Description
You are given a tree (an acyclic undirected connected graph) with N nodes, and edges numbered 1, 2, 3...N-1.
We will ask you to perfrom some instructions of the following form:
The first line of input contains an integer t, the number of test cases (t <= 20). t test cases follow.
For each test case:
There is one blank line between successive tests.
For each "QUERY" operation, write one integer representing its result.
Input: 1 3 1 2 1 2 3 2 QUERY 1 2 CHANGE 1 3 QUERY 1 2 DONE Output: 1 3
本来应该写树链剖分的，但既然要练LCT就敲敲咯……也是调了蛮久
#include<cstdio> #include<cstring> #include<algorithm> #define MN 10010 using namespace std; int p,ca,f; inline int read(){ p=0;ca=getchar();f=1; while(ca<‘0‘||ca>‘9‘) {if (ca==‘-‘) f=-1;ca=getchar();} while(ca>=‘0‘&&ca<=‘9‘) p=p*10+ca-48,ca=getchar(); return p*f; } struct na{ int y,ne,c,nu; }b[MN*2]; int fa[MN],n,t,x,y,c,l[MN],r[MN],num,id[MN],key[MN],ch[MN][2],ma[MN]; bool rt[MN]; inline int max(int a,int b){return a>b?a:b;} inline void update(int x){ ma[x]=max(max(ma[ch[x][0]],ma[ch[x][1]]),key[x]); } inline void rot(int x){ int y=fa[x],kind=ch[y][1]==x; fa[x]=fa[y]; fa[y]=x; ch[y][kind]=ch[x][!kind]; fa[ch[y][kind]]=y; ch[x][!kind]=y; if(rt[y]) rt[y]=0,rt[x]=1;else ch[fa[x]][ch[fa[x]][1]==y]=x; update(y);update(x); } inline void splay(int x){ while(!rt[x]){ if (rt[fa[x]]) rot(x);else if ((ch[fa[fa[x]]][1]==fa[x])==(ch[fa[x]][1]==x)) rot(fa[x]),rot(x);else rot(x),rot(x); } } inline void acc(int u){ int x=0; while(u){ splay(u); rt[ch[u][1]]=1;rt[ch[u][1]=x]=0; update(u); u=fa[x=u]; } } inline void change(int x,int c){ acc(x); key[x]=c; update(x); } inline void lca(int &u,int &v){ acc(v);v=0; while(u){ splay(u); if (!fa[u]) break; rt[ch[u][1]]=1; rt[ch[u][1]=v]=0; update(u); u=fa[v=u]; } } inline int qu(int x,int y){ lca(x,y); return max(ma[y],ma[ch[x][1]]); } inline void in(int x,int y,int c,int nu){ num++; if (!l[x]) l[x]=num;else b[r[x]].ne=num; b[num].y=y;b[num].c=c;b[num].ne=0;b[num].nu=nu;r[x]=num; } inline void dfs(int x){ for (int i=l[x];i;i=b[i].ne) if (!fa[b[i].y]){ fa[b[i].y]=x; id[b[i].nu]=b[i].y; key[b[i].y]=b[i].c; dfs(b[i].y); } } char ss[10]; int main(){ t=read(); ma[0]=-1e9; while(t--){ num=0; memset(rt,1,sizeof(rt)); memset(fa,0,sizeof(fa)); memset(ch,0,sizeof(ch)); memset(l,0,sizeof(l)); n=read(); for (int i=1;i<n;i++){ x=read();y=read();c=read(); in(x,y,c,i); in(y,x,c,i); } fa[1]=-1; dfs(1); fa[1]=0; for(;;){ scanf("%s",ss); if (ss[0]==‘D‘) break; x=read();y=read(); if (ss[0]==‘Q‘) printf("%d\n",qu(x,y));else change(id[x],y); } } }
原文：http://www.cnblogs.com/Enceladus/p/5239959.html