题意

给棵n个点的树。边有边权然后有三种操作

1、CHANGE i v 将编号为i的边权变为v

2、NEGATE a b 将a到b的所有边权变为相反数。

3、QUERY a b 查询a b路径的最大边权。

（n，q<=10000)

题解

树剖裸题。

边权下放。线段树记录最大值最小值即可。

1 #include
     
        2 #include
      
         3 #include
       
          4 #include
        
           5 #include
         
            6 using namespace std;  7 const int N=10010;  8 int cnt,head[N];  9 int size[N],fa[N],dep[N],ww[N],son[N],ide[N]; 10 int top[N],id[N],tot,w[N]; 11 int t,n; 12 char s[100];  13 struct edge{ 14     int to,nxt,w,id; 15 }e[N*3]; 16 void add(int u,int v,int w,int id){ 17     cnt++; 18     e[cnt].nxt=head[u]; 19     e[cnt].to=v; 20     e[cnt].w=w; 21     e[cnt].id=id; 22     head[u]=cnt; 23 } 24 struct tree{ 25     int l,r,maxx,minn,lazy; 26 }tr[N*8]; 27 void update(int now){ 28     tr[now].maxx=max(tr[now*2].maxx,tr[now*2+1].maxx); 29     tr[now].minn=min(tr[now*2].minn,tr[now*2+1].minn); 30 } 31 void pushdown(int now){ 32     if(tr[now].lazy==0)return; 33     int hh=tr[now*2].maxx; 34     tr[now*2].maxx=-tr[now*2].minn; 35     tr[now*2].minn=-hh; 36     hh=tr[now*2+1].maxx; 37     tr[now*2+1].maxx=-tr[now*2+1].minn; 38     tr[now*2+1].minn=-hh; 39     tr[now*2].lazy^=1; 40     tr[now*2+1].lazy^=1; 41     tr[now].lazy=0; 42 } 43 void dfs1(int u,int f,int deep){ 44     size[u]=1; 45     fa[u]=f; 46     dep[u]=deep; 47     int maxson=-1; 48     for(int i=head[u];i;i=e[i].nxt){ 49         int v=e[i].to; 50         if(v==f)continue; 51         ww[v]=e[i].w; 52         ide[e[i].id]=v; 53         dfs1(v,u,deep+1); 54         size[u]+=size[v]; 55         if(size[v]>maxson){ 56             son[u]=v; 57             maxson=size[v]; 58         } 59     } 60 } 61 void dfs2(int u,int tp){ 62     top[u]=tp; 63     id[u]=++tot; 64     w[tot]=ww[u]; 65     if(!son[u])return; 66     dfs2(son[u],tp); 67     for(int i=head[u];i;i=e[i].nxt){ 68         int v=e[i].to; 69         if(v==fa[u]||v==son[u])continue; 70         dfs2(v,v); 71     } 72 }  73 void build(int l,int r,int now){ 74     tr[now].l=l;tr[now].r=r; 75     tr[now].maxx=tr[now].lazy=tr[now].minn=0; 76     if(l==r){ 77         tr[now].maxx=tr[now].minn=w[l]; 78         return; 79     } 80     int mid=(l+r)>>1; 81     build(l,mid,now*2); 82     build(mid+1,r,now*2+1); 83     update(now); 84 } 85 int getmax(int l,int r,int now){ 86     pushdown(now);  87     if(tr[now].l==l&&tr[now].r==r){ 88         return tr[now].maxx; 89     } 90     int mid=(tr[now].l+tr[now].r)>>1; 91     if(l>mid)return getmax(l,r,now*2+1); 92     else if(r<=mid)return getmax(l,r,now*2); 93     else { 94         return max(getmax(l,mid,now*2),getmax(mid+1,r,now*2+1)); 95     } 96 } 97 void change(int x,int y,int now){ 98     pushdown(now); 99     if(tr[now].l==tr[now].r){100         tr[now].maxx=tr[now].minn=y;101         return;102     }103     int mid=(tr[now].l+tr[now].r)>>1;104     if(x>mid)change(x,y,now*2+1);105     else if(x<=mid)change(x,y,now*2);106     update(now); 107 }108 void getfan(int l,int r,int now){109     pushdown(now);110     if(tr[now].l==l&&tr[now].r==r){111         tr[now].lazy^=1;112         int hh=tr[now].maxx;113         tr[now].maxx=-tr[now].minn;114         tr[now].minn=-hh;115         return;116     }117     int mid=(tr[now].l+tr[now].r)>>1;118     if(l>mid)getfan(l,r,now*2+1);119     else if(r<=mid)getfan(l,r,now*2);120     else{121         getfan(l,mid,now*2);122         getfan(mid+1,r,now*2+1); 123     } 124     update(now);125 }126 int getlca(int x,int y){127     while(top[x]!=top[y]){128         if(dep[top[x]]
          
           dep[y])swap(x,y);143 ans=max(ans,getmax(id[x]+1,id[y],1));144 return ans;145 }146 void getfanl(int x,int y){147 while(top[x]!=top[y]){148 if(dep[top[x]]
           
            dep[y])swap(x,y);154 getfan(id[x]+1,id[y],1);155 }156 int main(){157 scanf("%d",&t);158 for(int z=1;z<=t;z++){159 scanf("%d",&n);160 memset(head,0,sizeof(head));161 memset(son,0,sizeof(son));162 memset(dep,0,sizeof(dep));163 memset(fa,0,sizeof(fa));164 memset(size,0,sizeof(size));165 memset(ide,0,sizeof(ide));166 memset(w,0,sizeof(w));167 memset(ww,0,sizeof(ww));168 memset(id,0,sizeof(id));169 memset(top,0,sizeof(top));170 tot=0;171 cnt=0;172 for(int i=1;i<=n-1;i++){173 int u,v,w;174 scanf("%d%d%d",&u,&v,&w);175 add(u,v,w,i);176 add(v,u,w,i);177 }178 dfs1(1,0,1);179 dfs2(1,1); 180 build(1,n,1);181 while(scanf("%s",&s)!=EOF){182 if(s[0]=='D')break;183 if(s[0]=='Q'){184 int x,y;185 scanf("%d%d",&x,&y);186 int LCA=getlca(x,y);187 printf("%d\n",max(getmaxl(LCA,x),getmaxl(LCA,y)));188 }189 else if(s[0]=='C'){190 int x,y;191 scanf("%d%d",&x,&y);192 change(id[ide[x]],y,1);193 }194 else if(s[0]=='N'){195 int x,y;196 scanf("%d%d",&x,&y);197 int LCA=getlca(x,y);198 getfanl(LCA,x);199 getfanl(LCA,y);200 }201 }202 }203 return 0;204 }