| 记录编号 |
438253 |
评测结果 |
AAAAAAAAAA |
| 题目名称 |
[国家集训队2011]旅游 |
最终得分 |
100 |
| 用户昵称 |
 ~玖湫~ |
是否通过 |
通过 |
| 代码语言 |
C++ |
运行时间 |
0.436 s |
| 提交时间 |
2017-08-15 17:44:37 |
内存使用 |
13.29 MiB |
显示代码纯文本
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
const int M=100000+10;
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
char s[5];
int n,m,num,cnt;
int head[2*M],size[M],dep[M],son[M],fa[M],v[M],top[M],id[M],pos[M];
int sum[4*M],mx[4*M],mn[4*M],adda[4*M];
struct DATE{int fr,to,w,last;}date[2*M];
inline int read(){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}
return x*f;
}
inline void add(int x,int y,int z){
date[++num]=(DATE){x,y,z,head[x]};
head[x]=num;
}
void dfs1(int x){
size[x]=1;
for(int i=head[x];i;i=date[i].last){
int to=date[i].to,w=date[i].w;
if(to!=fa[x]){
fa[to]=x;dep[to]=dep[x]+1;v[to]=w;
dfs1(to);size[x]+=size[to];
if(size[son[x]]<size[to]) son[x]=to;
}
}
}
void dfs2(int x,int tp){
top[x]=tp;id[x]=++cnt;pos[cnt]=x;
if(son[x]) dfs2(son[x],tp);
for(int i=head[x];i;i=date[i].last){
int to=date[i].to;
if(to!=fa[x]&&to!=son[x]) dfs2(to,to);
}
}
void pushup(int rt){
int ls=rt<<1,rs=rt<<1|1;
sum[rt]=sum[ls]+sum[rs];
mx[rt]=max(mx[ls],mx[rs]);
mn[rt]=min(mn[ls],mn[rs]);
}
void pushdown(int rt){
if(adda[rt]){
int ls=rt<<1,rs=rt<<1|1;adda[rt]^=1;
int tmp=mn[ls];adda[ls]^=1;
sum[ls]*=-1;mn[ls]=-mx[ls];mx[ls]=-tmp;
tmp=mn[rs];adda[rs]^=1;
sum[rs]*=-1;mn[rs]=-mx[rs];mx[rs]=-tmp;
}
}
void bt(int rt,int l,int r){
if(l==r) {sum[rt]=mn[rt]=mx[rt]=v[pos[l]];return ;}
int mid=l+r>>1;bt(lson);bt(rson);pushup(rt);
}
void change(int pos,int zhi,int rt,int l,int r){
if(l==r){sum[rt]=mn[rt]=mx[rt]=zhi;return ;}
pushdown(rt);int mid=l+r>>1;
if(pos<=mid) change(pos,zhi,lson);
else change(pos,zhi,rson);
pushup(rt);
}
void neg(int s,int t,int rt,int l,int r){
if(s<=l&&r<=t){
int tmp=mn[rt];adda[rt]^=1;
sum[rt]*=-1;mn[rt]=-mx[rt];mx[rt]=-tmp;
return ;
}
pushdown(rt);int mid=l+r>>1;
if(s<=mid) neg(s,t,lson);
if(t>mid) neg(s,t,rson);
pushup(rt);
}
int get_min(int s,int t,int rt,int l,int r){
if(s<=l&&r<=t) return mn[rt];
pushdown(rt);
int mid=l+r>>1; int res=1<<30;
if(s<=mid) res=min(res,get_min(s,t,lson));
if(t>mid) res=min(res,get_min(s,t,rson));
return res;
}
int get_max(int s,int t,int rt,int l,int r){
if(s<=l&&r<=t) return mx[rt];
pushdown(rt);
int mid=l+r>>1; int res=1<<31;
if(s<=mid) res=max(res,get_max(s,t,lson));
if(t>mid) res=max(res,get_max(s,t,rson));
return res;
}
int get_sum(int s,int t,int rt,int l,int r){
if(s<=l&&r<=t) return sum[rt];
pushdown(rt);
int mid=l+r>>1; int res=0;
if(s<=mid) res+=get_sum(s,t,lson);
if(t>mid) res+=get_sum(s,t,rson);
return res;
}
void Neg(int x,int y){
int fx=top[x],fy=top[y];
while(fx!=fy){
if(dep[fx]<dep[fy])
swap(x,y),swap(fx,fy);
neg(id[fx],id[x],1,1,n);
x=fa[fx];fx=top[x];
}
if(dep[x]>dep[y]) swap(x,y);
neg(id[x]+1,id[y],1,1,n);
}
int _Max(int x,int y){
int fx=top[x],fy=top[y];int res=1<<31;
while(fx!=fy){
if(dep[fx]<dep[fy])
swap(x,y),swap(fx,fy);
res=max(res,get_max(id[fx],id[x],1,1,n));
x=fa[fx];fx=top[x];
}
if(dep[x]>dep[y]) swap(x,y);
res=max(res,get_max(id[x]+1,id[y],1,1,n));
return res;
}
int _Min(int x,int y){
int fx=top[x],fy=top[y];int res=1<<30;
while(fx!=fy){
if(dep[fx]<dep[fy])
swap(x,y),swap(fx,fy);
res=min(res,get_min(id[fx],id[x],1,1,n));
x=fa[fx];fx=top[x];
}
if(dep[x]>dep[y]) swap(x,y);
res=min(res,get_min(id[x]+1,id[y],1,1,n));
return res;
}
int _Sum(int x,int y){
int fx=top[x],fy=top[y];int res=0;
while(fx!=fy){
if(dep[fx]<dep[fy])
swap(x,y),swap(fx,fy);
res+=get_sum(id[fx],id[x],1,1,n);
x=fa[fx];fx=top[x];
}
if(dep[x]>dep[y]) swap(x,y);
res+=get_sum(id[x]+1,id[y],1,1,n);
return res;
}
int main(){
freopen("nt2011_travel.in","r",stdin);
freopen("nt2011_travel.out","w",stdout);
n=read();int aa,bb,cc;
for(int i=1;i<n;i++){
aa=read();bb=read();cc=read();
add(aa,bb,cc);add(bb,aa,cc);
}
dfs1(0);dfs2(0,0);bt(1,1,n);m=read();
while(m--){
scanf("%s",s);aa=read();bb=read();
if(s[0]=='N') {Neg(aa,bb);continue;}
if(s[0]=='C'){
int fr=date[2*aa].fr,to=date[2*aa].to;
if(fa[fr]==to) change(id[fr],bb,1,1,n);
else change(id[to],bb,1,1,n);
continue;
}
if(s[0]=='S') {printf("%d\n",_Sum(aa,bb));continue;}
if(s[1]=='A') {printf("%d\n",_Max(aa,bb));continue;}
if(s[1]=='I') {printf("%d\n",_Min(aa,bb));continue;}
}
return 0;
}