You are given a tree (an acyclic undirected connected graph) with N nodes, and nodes numbered 1,2,3...,N. Each edge has an integer value assigned to it(note that the value can be negative). Each node has a color, white or black. We define dist(a, b) as the sum of the value of the edges on the path from node a to node b.
All the nodes are white initially.
We will ask you to perfrom some instructions of the following form:
For each "A" operation, write one integer representing its result. If there is no white node in the tree, you should write "They have disappeared.".
Input: 3 1 2 1 1 3 1 7 A C 1 A C 2 A C 3 A Output: 2 2 0 They have disappeared.
Some new test data cases were added on Apr.29.2008, all the solutions have been rejudged.
树 Link cut tree
查动态点分治时候在别的博客看到一个LCT做Qtree的专题，心生敬仰于是学（chao）了一发。
结论是相比之下还是点分治好写啊，这个状态更新神烦，如果不标准代码比对，我估计得调几个小时吧……
--------
大致就是，把边权迁移到子结点上，先建好LCT。Splay树是二叉树，那么就把当前未激活的边全都扔到set里记录区间答案，然后像平衡树/线段树维护最大子串和那样，记录上边来的最长链，下边来的最长链，左边来的最长链，右边来的最长链……，以及当前结点保存的边长等信息。如果链是从原树的祖先方向来的，维护时候要加那个被迁移的边权，如果是从子孙方向来的，因为下面加过了所以不用再加……
之后花式更新即可。
那个边扔到set里的操作，有人说是传说中的虚边……ダメだ 知らないだ……
n*(logn)^2卡常预警。据说是因为树浅时set多但LCT操作少，而树深时LCT操作多但set小，均摊下来不会超时。
↑不会算复杂度的我只能把这当成玄学
1 /*by SilverN*/ 2 #include<algorithm> 3 #include<iostream> 4 #include<cstring> 5 #include<cstdio> 6 #include<cmath> 7 #include<vector> 8 #include<set> 9 using namespace std; 10 const int INF=1e8; 11 const int mxn=200010; 12 int read(){ 13 int x=0,f=1;char ch=getchar(); 14 while(ch<‘0‘ || ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} 15 while(ch>=‘0‘ && ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} 16 return x*f; 17 } 18 int fir(multiset<int> &s){return s.size()? *s.rbegin():-INF;} 19 int sec(multiset<int> &s){return s.size()>1? *(++s.rbegin()):-INF;} 20 struct edge{int v,nxt,w;}e[mxn<<1]; 21 int hd[mxn],mct=0; 22 void add_edge(int u,int v,int w){ 23 e[++mct].v=v;e[mct].nxt=hd[u];e[mct].w=w;hd[u]=mct;return; 24 } 25 int col[mxn],w[mxn]; 26 struct LCT{ 27 multiset<int>chain[mxn],pt[mxn]; 28 int ch[mxn][2],fa[mxn]; 29 int len[mxn],L[mxn],R[mxn],mians[mxn],sum[mxn],ans; 30 bool rev[mxn]; 31 void init(int n){for(int i=0;i<=n;i++)L[i]=R[i]=mians[i]=-INF;} 32 inline bool isroot(int x){return ((ch[fa[x]][0]!=x) && (ch[fa[x]][1]!=x));} 33 void pushup(int x){ 34 int lc=ch[x][0],rc=ch[x][1]; 35 sum[x]=sum[lc]+sum[rc]+len[x]; 36 int cmi=max(w[x],fir(chain[x])); 37 // printf("tst %d: lc:%d rc:%d sum:%d cmi:%d\n",x,lc,rc,sum[x],cmi); 38 // printf(" L rc:%d R lc:%d\n",L[rc],R[lc]); 39 int La=max(cmi,R[lc]+len[x]);//左子树(深度更浅的地方) 40 int Ra=max(cmi,L[rc]);//右子树 41 L[x]=max(L[lc],sum[lc]+len[x]+Ra); 42 R[x]=max(R[rc],sum[rc]+La); 43 // printf(" L:%d R:%d\n",L[x],R[x]); 44 mians[x]=max(mians[lc],mians[rc]); 45 mians[x]=max(mians[x],max(R[lc]+len[x]+Ra,L[rc]+La)); 46 mians[x]=max(mians[x],fir(pt[x])); 47 mians[x]=max(mians[x],fir(chain[x])+sec(chain[x])); 48 if(w[x]==0)mians[x]=max(w[x],max(mians[x],fir(chain[x]))); 49 return; 50 } 51 void rotate(int x){ 52 int y=fa[x],z=fa[y],lc,rc; 53 if(ch[y][0]==x)lc=0;else lc=1;rc=lc^1; 54 if(!isroot(y))ch[z][ch[z][1]==y]=x; 55 fa[x]=z;fa[y]=x; 56 ch[y][lc]=ch[x][rc];fa[ch[x][rc]]=y; 57 ch[x][rc]=y; 58 pushup(y); 59 return; 60 } 61 // int st[mxn],top; 62 void Splay(int x){ 63 while(!isroot(x)){ 64 int y=fa[x],z=fa[y]; 65 if(!isroot(y)){ 66 if((ch[z][0]==y)^(ch[y][0]==x))rotate(x); 67 else rotate(y); 68 } 69 rotate(x); 70 } 71 pushup(x); 72 } 73 void access(int x){ 74 int y=0; 75 for(;x;x=fa[x]){ 76 Splay(x); 77 if(ch[x][1]){ 78 pt[x].insert(mians[ch[x][1]]); 79 chain[x].insert(L[ch[x][1]]); 80 } 81 if(y){ 82 pt[x].erase(pt[x].find(mians[y])); 83 chain[x].erase(chain[x].find(L[y])); 84 } 85 ch[x][1]=y; 86 pushup(x); 87 y=x; 88 } 89 } 90 void change(int x){ 91 access(x);Splay(x); 92 col[x]^=1;if(!col[x])w[x]=0;else w[x]=-INF; 93 pushup(x); 94 ans=mians[x]; 95 } 96 /* void query(int x){ 97 access(x);Splay(x); 98 pushup(x); 99 ans=mians[x]; 100 }*/ 101 }LT; 102 void DFS(int u,int fa){ 103 for(int i=hd[u];i;i=e[i].nxt){ 104 if(e[i].v==fa)continue;int v=e[i].v; 105 LT.fa[v]=u; 106 LT.len[v]=e[i].w; 107 DFS(v,u); 108 LT.chain[u].insert(LT.L[v]); 109 LT.pt[u].insert(LT.mians[v]); 110 } 111 LT.pushup(u); 112 return; 113 } 114 int n,Q; 115 int main(){ 116 int i,j,u,v,vl; 117 n=read(); 118 for(i=1;i<n;i++){ 119 u=read();v=read();vl=read(); 120 add_edge(u,v,vl); 121 add_edge(v,u,vl); 122 } 123 LT.init(n); 124 // for(i=1;i<=n;i++)col[i]=0; 125 DFS(1,0); 126 LT.ans=LT.mians[1]; 127 // printf("LT:%d\n",LT.ans); 128 Q=read();char op[2]; 129 while(Q--){ 130 scanf("%s",op); 131 if(op[0]==‘C‘)v=read(),LT.change(v); 132 else{ 133 // LT.query(v); 134 if(LT.ans<0)printf("They have disappeared.\n"); 135 else printf("%d\n",LT.ans); 136 } 137 } 138 return 0; 139 }
SPOJ QTREE4 SPOJ Query on a tree IV
原文：http://www.cnblogs.com/SilverNebula/p/6440237.html