| 记录编号 |
400679 |
评测结果 |
AAAAAAAAAA |
| 题目名称 |
[国家集训队2011]旅游 |
最终得分 |
100 |
| 用户昵称 |
 WildRage |
是否通过 |
通过 |
| 代码语言 |
C++ |
运行时间 |
0.465 s |
| 提交时间 |
2017-04-30 19:04:45 |
内存使用 |
11.76 MiB |
显示代码纯文本
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int N=100010;
struct egde{
int v,next,END;
}v[N<<1];
int first[N],p=1;
int n;
int dep[N],size[N],fa[N],id[N],son[N],val[N],top[N],num;
void add(int a,int b,int c){
v[p].END=b;
v[p].v=c;
v[p].next=first[a];
first[a]=p++;
}
void dfs1(int rt,int f,int dp){
dep[rt]=dp;
size[rt]=1;
son[rt]=0;
fa[rt]=f;
for(int i=first[rt];i!=-1;i=v[i].next){
if(v[i].END==f)continue;
dfs1(v[i].END,rt,dp+1);
val[v[i].END]=v[i].v;
size[rt]+=size[v[i].END];
son[rt]= size[v[i].END]>size[son[rt]] ? v[i].END : son[rt];
}
}
void dfs2(int rt,int tp){
top[rt]=tp;
id[rt]=++num;
if(son[rt])dfs2(son[rt],tp);
for(int i=first[rt];i!=-1;i=v[i].next){
if(v[i].END==fa[rt]||v[i].END==son[rt])continue;
dfs2(v[i].END,v[i].END);
}
}
#define lch l,m,rt<<1
#define rch m+1,r,rt<<1|1
int maxn[N<<2],minn[N<<2],sumn[N<<2],change[N<<2];
int sum(int a,int b){return a+b;}
void Pushup(int rt){
maxn[rt]=max(maxn[rt<<1],maxn[rt<<1|1]);
minn[rt]=min(minn[rt<<1],minn[rt<<1|1]);
sumn[rt]=sum(sumn[rt<<1],sumn[rt<<1|1]);
}
void Pushdown(int rt){
if(change[rt]){
change[rt<<1]^=1,change[rt<<1|1]^=1;
sumn[rt<<1]=-sumn[rt<<1];
sumn[rt<<1|1]=-sumn[rt<<1|1];
int o=maxn[rt<<1];
maxn[rt<<1]=-minn[rt<<1];
minn[rt<<1]=-o;
o=maxn[rt<<1|1];
maxn[rt<<1|1]=-minn[rt<<1|1];
minn[rt<<1|1]=-o;
change[rt]=0;
}
}
void update(int i,int c,int l,int r,int rt){
if(l==r){maxn[rt]=c;minn[rt]=c;sumn[rt]=c;change[rt]=0;return;}
Pushdown(rt);
int m=(l+r)>>1;
if(i<=m) update(i,c,lch);
else update(i,c,rch);
Pushup(rt);
}
void Update(int L,int R,int l,int r,int rt){
if(L<=l&&R>=r){
change[rt]^=1;
sumn[rt]=-sumn[rt];
int o=maxn[rt];
maxn[rt]=-minn[rt];
minn[rt]=-o;
return;
}
Pushdown(rt);
int m=(l+r)>>1;
if(L<=m) Update(L,R,lch);
if(R>m) Update(L,R,rch);
Pushup(rt);
}
int max(int L,int R,int l,int r,int rt){
if(L<=l&&R>=r)return maxn[rt];
int m=(l+r)>>1;
int ans=0x80808080;
Pushdown(rt);
if(L<=m) ans=max(ans,max(L,R,lch));
if(R>m) ans=max(ans,max(L,R,rch));
return ans;
}
int sum(int L,int R,int l,int r,int rt){
if(L<=l&&R>=r)return sumn[rt];
int m=(l+r)>>1;
int ans=0;
Pushdown(rt);
if(L<=m) ans+=sum(L,R,lch);
if(R>m) ans+=sum(L,R,rch);
return ans;
}
int min(int L,int R,int l,int r,int rt){
if(L<=l&&R>=r)return minn[rt];
int m=(l+r)>>1;
int ans=0x7f7f7f7f;
Pushdown(rt);
if(L<=m) ans=min(ans,min(L,R,lch));
if(R>m) ans=min(ans,min(L,R,rch));
return ans;
}
int Max(int x,int y){
int ans=0x80808080;
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]])swap(x,y);
ans=max(ans,max(id[top[x]],id[x],1,n,1));
x=fa[top[x]];
}
if(dep[x]>dep[y])swap(x,y);
if(x!=y)ans=max(ans,max(id[x]+1,id[y],1,n,1));
return ans;
}
int Min(int x,int y){
int ans=0x7f7f7f7f;
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]])swap(x,y);
ans=min(ans,min(id[top[x]],id[x],1,n,1));
x=fa[top[x]];
}
if(dep[x]>dep[y])swap(x,y);
if(x!=y)ans=min(ans,min(id[x]+1,id[y],1,n,1));
return ans;
}
int Sum(int x,int y){
int ans=0;
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]])swap(x,y);
ans=sum(ans,sum(id[top[x]],id[x],1,n,1));
x=fa[top[x]];
}
if(dep[x]>dep[y])swap(x,y);
if(x!=y)ans=sum(ans,sum(id[x]+1,id[y],1,n,1));
return ans;
}
void Update(int x,int y){
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]])swap(x,y);
Update(id[top[x]],id[x],1,n,1);
x=fa[top[x]];
}
if(dep[x]>dep[y])swap(x,y);
if(x!=y)Update(id[x]+1,id[y],1,n,1);
}
int main(){
memset(maxn,0x80,sizeof(maxn));
memset(minn,0x3f,sizeof(minn));
memset(first,-1,sizeof(first));
freopen("nt2011_travel.in","r",stdin);
freopen("nt2011_travel.out","w",stdout);
scanf("%d",&n);
int a,b,c;
for(int i=1;i<=n-1;i++){
scanf("%d%d%d",&a,&b,&c);
add(a,b,c);
add(b,a,c);
}
dfs1(0,0,1);
dfs2(0,0);
for(int i=1;i<n;i++){
update(id[i],val[i],1,n,1);
}
int m;
scanf("%d",&m);
char op[5];
int i,w;
while(m--){
scanf("%s",op);
if(op[0]=='C'){
scanf("%d%d",&i,&w);
a=v[i<<1].END;
b=v[(i<<1)-1].END;
if(dep[a]<dep[b])a=b;
update(id[a],w,1,n,1);
}
else if(op[0]=='N'){
scanf("%d%d",&a,&b);
Update(a,b);
}
else if(op[0]=='S'){
scanf("%d%d",&a,&b);
printf("%d\n",Sum(a,b));
}
else if(op[1]=='A'){
scanf("%d%d",&a,&b);
printf("%d\n",Max(a,b));
}
else {
scanf("%d%d",&a,&b);
printf("%d\n",Min(a,b));
}
}
}