Description
You are given a tree with N nodes. The tree’s nodes are numbered 1 through N and its edges are numbered 1 through N ? 1. Each edge is associated with a weight. Then you are to execute a series of instructions on the tree. The instructions can be one of the following forms:
CHANGE i v |
Change the weight of the ith edge to v |
NEGATE a b |
Negate the weight of every edge on the path from a to b |
QUERY a b |
Find the maximum weight of edges on the path from a to b |
Input
The input contains multiple test cases. The first line of input contains an integer t (t ≤ 20), the number of test cases. Then follow the test cases.
Each test case is preceded by an empty line. The first nonempty line of its contains N (N ≤ 10,000). The next N ? 1 lines each contains three integers a, b and c, describing an edge connecting nodes a and bwith weight c. The edges are numbered in the order they appear in the input. Below them are the instructions, each sticking to the specification above. A lines with the word “DONE” ends the test case.
Output
For each “QUERY” instruction, output the result on a separate line.
Sample Input
13 1 2 1 2 3 2 QUERY 1 2 CHANGE 1 3 QUERY 1 2 DONE
Sample Output
1 3
Source
POJ Monthly--2007.06.03, Lei, Tao
~~~~~~~~~~~~~~~~~~~~~~~~~~~
树链剖分~
——5.25 遗留的千年老问题终于解决掉了……泪流满面……
这道题就比SPOJ QTREE多了一个反转操作(即max=-min,min=-max的操作),但是完全不能用那种方法。修改需要求lca后把答案分为两条直链分别计算。我们在树上打上懒标记,就能很方便地更新结果(但是也很容易出错)。
注意:
1.分清k<<1和a[k].l;
2.加边一定要在dfs的时候加,在主函数里面会出错,我不知道为什么。
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
#define inf 999999999int t,n,x,y,z,fi[10001],w[20001],ne[20001],v[20001],cnt,dep[10001],son[10001],top[10001],siz[10001],id[10001],to[10001],fa[10001][14];
char ch[10];struct node1{int x,y,val;
}ed[20001];struct node{int l,r,mn,mx;bool tag;
}a[10001<<2];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<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;
}void add(int u,int vv,int val)
{w[++cnt]=vv;ne[cnt]=fi[u];fi[u]=cnt;v[cnt]=val;w[++cnt]=u;ne[cnt]=fi[vv];fi[vv]=cnt;v[cnt]=val;
}void update(int k)
{a[k].mn=min(a[k<<1].mn,a[k<<1|1].mn);a[k].mx=max(a[k<<1].mx,a[k<<1|1].mx);
}void solve(node &u)
{swap(u.mn,u.mx);u.mn*=-1;u.mx*=-1;
}void pushdown(int k)
{int l=k<<1,r=k<<1|1;a[k].tag=0;a[l].tag^=1;a[r].tag^=1;solve(a[l]);solve(a[r]);
}void build(int l,int r,int k)
{a[k].l=l;a[k].r=r;a[k].tag=0;a[k].mn=inf;a[k].mx=-inf;if(l==r) return;int mid=l+r>>1;build(l,mid,k<<1);build(mid+1,r,k<<1|1);
}void chan(int k,int u,int v)
{int l=a[k].l,r=a[k].r,mid=l+r>>1;if(l==r){a[k].mn=a[k].mx=v;return;}if(a[k].tag) pushdown(k);if(u<=mid) chan(k<<1,u,v);else chan(k<<1|1,u,v);update(k);
}void dfs1(int u)
{for(int i=1;i<=13;i++) fa[u][i]=fa[fa[u][i-1]][i-1];son[u]=0;siz[u]=1;for(int i=fi[u];i;i=ne[i])if(w[i]!=fa[u][0]){fa[w[i]][0]=u;dep[w[i]]=dep[u]+1;dfs1(w[i]);siz[u]+=siz[w[i]];if(!son[u] || siz[son[u]]<siz[w[i]]) son[u]=w[i];}
}void dfs2(int u,int la)
{top[u]=la;id[u]=++cnt;if(son[u]) dfs2(son[u],la);for(int i=fi[u];i;i=ne[i])if(w[i]!=son[u] && w[i]!=fa[u][0]) dfs2(w[i],w[i]);else if(w[i]==fa[u][0]){to[i>>1]=id[u];chan(1,id[u],v[i]);}
}void rever(int k,int u,int v)
{int l=a[k].l,r=a[k].r,mid=l+r>>1;if(a[k].tag && l!=r) pushdown(k);if(l>=u && r<=v){solve(a[k]);a[k].tag=1;return;}if(u<=mid) rever(k<<1,u,v);if(v>mid) rever(k<<1|1,u,v);update(k);
}int lca(int u,int v)
{if(dep[u]<dep[v]) swap(u,v);for(int i=13;~i;i--) if(dep[fa[u][i]]>=dep[v]) u=fa[u][i];if(u==v) return u;for(int i=13;~i;i--) if(fa[u][i]!=fa[v][i]) u=fa[u][i],v=fa[v][i];return fa[u][0];
}int cal(int k,int u,int v)
{int l=a[k].l,r=a[k].r,mid=l+r>>1,now=-inf;if(a[k].tag && l!=r) pushdown(k);if(l>=u && r<=v) return a[k].mx;if(mid>=u) now=max(now,cal(k<<1,u,v));if(v>mid) now=max(now,cal(k<<1|1,u,v));return now;
}int mx(int u,int v)
{int now=-inf;while(top[u]!=top[v]){now=max(now,cal(1,id[top[u]],id[u]));u=fa[top[u]][0];}if(id[v]+1<=id[u]) now=max(now,cal(1,id[v]+1,id[u]));return now;
}int rev(int u,int v)
{while(top[u]!=top[v]){rever(1,id[top[u]],id[u]);u=fa[top[u]][0];}if(id[v]+1<=id[u]) rever(1,id[v]+1,id[u]);
}int main()
{t=read();while(t--){memset(fa,0,sizeof(fa));cnt=0;memset(fi,0,sizeof(fi));n=read();for(int i=1;i<n;i++){x=read(),y=read(),z=read(),add(x,y,z);ed[i]=(node1){x,y,z};}cnt=0;build(1,n,1);dfs1(1);dfs2(1,1);while(scanf("%s",ch)){if(ch[0]=='D') break;x=read();y=read();if(ch[0]=='C') chan(1,id[ed[x].x],y);else if(ch[0]=='N'){int k=lca(x,y);rev(x,k);rev(y,k);}else{int k=lca(x,y);printf("%d\n",max(mx(x,k),mx(y,k)));}}}return 0;
}