样例已过,全wa,和正确代码打对拍,删“C”操作完全相同,但是找不到“C”操作错在哪里……
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>+
using namespace std;
const int N=200005;
int n,m,idx,cnt;
struct node{
int to,next;
int w;
}seg[N<<1];
int e[N],ln[N],head[N];
struct Tree{
int l,r,rev;
int sum,maxv,minv;
}tr[N<<2];
int id[N],fa[N],nw[N];
int dep[N],top[N],son[N],siz[N];
struct Oper{
int sum;
int minv,maxv;
};
void add(int u,int v,int w)
{
seg[++idx].to=v;
seg[idx].w=w;
seg[idx].next=head[u];
head[u]=idx;
}
void dfs1(int u,int p,int depth,int edge)
{
siz[u]=1,fa[u]=p,dep[u]=depth,e[u]=edge,ln[edge]=u;
for(int i=head[u],v;i;i=seg[i].next)
{
v=seg[i].to;
if(v==p)continue;
dfs1(v,u,depth+1,i);
siz[u]+=siz[v];
if(siz[v]>siz[son[u]])son[u]=v;
}
}
void dfs2(int u,int t)
{
top[u]=t,id[u]=++cnt,nw[cnt]=seg[e[u]].w;
if(!son[u])return;
dfs2(son[u],t);
for(int i=head[u],v;i;i=seg[i].next)
{
v=seg[i].to;
if(v==fa[u]||v==son[u])continue;
dfs2(v,v);
}
}
inline void pushup(int x)
{
tr[x].sum=tr[x<<1].sum+tr[x<<1|1].sum;
tr[x].minv=min(tr[x<<1].minv,tr[x<<1|1].minv);
tr[x].maxv=max(tr[x<<1].maxv,tr[x<<1|1].maxv);
}
void build(int u,int l,int r)
{
tr[u].l=l,tr[u].r=r;
if(l==r)
{
tr[u].sum=nw[l];
tr[u].maxv=tr[u].minv=nw[r];
return;
}
int mid=(l+r)>>1;
build(u<<1,l,mid);
build(u<<1|1,mid+1,r);
pushup(u);
}
inline void change(int x,int k)
{
tr[x].sum=k;
tr[x].maxv=tr[x].minv=k;
}
inline void change_rev(int u)
{
tr[u].rev^=1;
tr[u].sum*=-1;
swap(tr[u].maxv,tr[u].minv);
tr[u].maxv*=-1,tr[u].minv*=-1;
}
void pushdown(int u)
{
if(!tr[u].rev)return;
tr[u].rev=0;
change_rev(u<<1);
change_rev(u<<1|1);
}
void change_pos(int u,int pos,int k)
{
if(tr[u].l==pos&&tr[u].r==pos)
{
change(u,k);
return;
}
pushdown(u);
int mid=(tr[u].l+tr[u].r)>>1;
if(pos<=mid)change_pos(u<<1,pos,k);
else change_pos(u<<1|1,pos,k);
pushup(u);
}
void update(int u,int l,int r)
{
if(l>r)return;
if(tr[u].l>=l&&tr[u].r<=r)
{
change_rev(u);
return;
}
pushdown(u);
int mid=(tr[u].l+tr[u].r)>>1;
if(l<=mid)update(u<<1,l,r);
if(r>mid)update(u<<1|1,l,r);
pushup(u);
}
void update_path(int u,int v)
{
while(top[u]!=top[v])
{
if(dep[top[u]]<dep[top[v]])swap(u,v);
update(1,id[top[u]],id[u]);
u=fa[top[u]];
}
if(dep[u]<dep[v])swap(u,v);
update(1,id[v]+1,id[u]);
}
Oper operator + (Oper a,Oper b)
{
a.sum+=b.sum;
a.maxv=max(a.maxv,b.maxv);
a.minv=min(a.minv,b.minv);
return a;
}
void print(Oper a)
{
printf("%d %d %d\n",a.sum,a.minv,a.maxv);
}
Oper query(int u,int l,int r)
{
if(l>r)return {0,1000,-1000};
if(tr[u].l>=l&&tr[u].r<=r)return {tr[u].sum,tr[u].minv,tr[u].maxv};
pushdown(u);
Oper opt={0,1000,-1000};
int mid=(tr[u].l+tr[u].r)>>1;
if(l<=mid)opt=opt+query(u<<1,l,r);
if(r>mid)opt=opt+query(u<<1|1,l,r);
// print(opt);
return opt;
}
Oper query_path(int u,int v)
{
Oper opt={0,1000,-1000};
while(top[u]!=top[v])
{
if(dep[top[u]]<dep[top[v]])swap(u,v);
opt=opt+query(1,id[top[u]],id[u]);
u=fa[top[u]];
// cout<<"---------------------------"<<endl;
// print(opt);
}
if(dep[u]<dep[v])swap(u,v);
opt=opt+query(1,id[v]+1,id[u]);
return opt;
}
int main()
{
freopen("1.out","w",stdout);
scanf("%d",&n);
for(int i=1,u,v,w;i<n;i++)
{
scanf("%d%d%d",&u,&v,&w);
add(u+1,v+1,w),add(v+1,u+1,w);
}
dfs1(1,0,1,0);
dfs2(1,1);
build(1,1,cnt);
scanf("%d",&m);
while(m--)
{
int x,y;
char op[5];
scanf("%s %d%d",op,&x,&y);
if(*op=='C')change_pos(1,id[ln[x]],y);
else if(*op=='N')update_path(x+1,y+1);
else
{
Oper opt=query_path(x+1,y+1);
// cout<<"-------------------------------------------------------------------------------"<<endl;
// print(opt);
if(!strcmp(op,"SUM"))printf("%d\n",opt.sum);
if(!strcmp(op,"MIN"))printf("%d\n",opt.minv);
if(!strcmp(op,"MAX"))printf("%d\n",opt.maxv);
}
// for(int i=1;i<8;i++)printf("%d %d %d %d %d %d %d\n",i,tr[i].l,tr[i].r,tr[i].minv,tr[i].maxv,tr[i].sum,tr[i].rev);
}
return 0;
}