spoj qtree IV

2666. Query on a tree IV

Problem code: QTREE4

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:

C a : change the color of node a.(from black to white or from white to black)
A : ask for the maximum dist(a, b), both of node a and node b must be white(a can be equal to b). Obviously, as long as there is a white node, the result will alway be non negative.

Input

In the first line there is an integer N (N <= 100000)
In the next N-1 lines, the i-th line describes the i-th edge: a line with three integers a b c denotes an edge between a, b of value c (-1000 <= c <= 1000)
In the next line, there is an integer Q denotes the number of instructions (Q <= 100000)
In the next Q lines, each line contains an instruction "C a" or "A"

Output

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.".

Example

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.


大意:
给出一棵树,每个点非白即黑.求树上最远的两个白点之间的距离,中间必须支持动态修改每个点的黑白状态.

思考:
树分治真是个好东西......
边分治有一个非常好的性质:就是一条边能将整棵树分成两个部分.(二分)
所以合并信息是非常方便的.

我们将每个点到中心边的距离求出来并且保存.对于每条中心边,用一个优先队列来保存对应的最优值.
最后我们合并答案即可.

但是边分治的缺点也显而易见.就是菊花树的时候复杂度经常退化.
那么怎么做呢? 我们将这棵树重构,就不会那么退化得厉害了.


代码比较慢,凑合着看....

  1 #include<cstdlib>
  2 #include<cstdio>
  3 #include<algorithm>
  4 #include<cstring>
  5 #include<queue>
  6 #include<cctype>
  7 #include<ctime>
  8 using namespace std;
  9 const int maxn = (int)4e5, inf = 0x3f3f3f3f;
 10 struct E{
 11     int t,w,last;
 12 }e[maxn * 8][3];
 13 int last[maxn * 8][3],edg[3]={1,1,1},ext;
 14 void add1(int x,int y,int w){
 15     e[++edg[ext]][ext] = (E){y,w,last[x][ext]}; last[x][ext] = edg[ext];
 16 }
 17 void add(int x,int y,int w){
 18     add1(x,y,w); add1(y,x,w);
 19 }
 20 int getint(){
 21     int ret = 0,t = 1; char ch = getchar();
 22     while(!isdigit(ch)) t = ch == '-' ? -1 : t, ch = getchar();
 23     while(isdigit(ch)) ret = ret * 10 + ch - '0', ch = getchar();
 24     return ret * t;
 25 }
 26 int n,img;
 27 int col[maxn * 4];
 28 void rebuild(int x,int fa){
 29     int las = x;
 30     for(int i = last[x][0]; i; i = e[i][0].last)
 31         if(e[i][0].t != fa){
 32             if(i == last[x][0]) add(x,e[i][0].t,e[i][0].w);
 33             else col[++img] = 1, add(las,img,0), add(img,e[i][0].t,e[i][0].w),las = img;
 34         }
 35     for(int i = last[x][0]; i; i = e[i][0].last)
 36         if(e[i][0].t != fa) rebuild(e[i][0].t, x);
 37 }
 38 struct D{    
 39     int x,dis;
 40     bool operator <(const D &b) const{
 41         return dis < b.dis;
 42     }
 43 };
 44 struct SEG{
 45     int ans;
 46     int l,r,mid;
 47     priority_queue<D>q;
 48     void pop(){
 49         while(!q.empty() && col[q.top().x] == 1) q.pop();
 50     }
 51 }T[maxn * 4];
 52 int cnt,mid,node,tmax,p;
 53 int sz[maxn * 4],vis[maxn * 8];
 54 void pushup(int x){
 55     T[x].ans = -1;
 56     T[x].pop();
 57     int l = T[x].l, r = T[x].r;
 58     if(l == 0 && r == 0){
 59         if(!T[x].q.empty()) T[x].ans = 0;
 60     }else{
 61         if(T[x].ans < T[l].ans) T[x].ans = T[l].ans;
 62         if(T[x].ans < T[r].ans) T[x].ans = T[r].ans;
 63         if(!T[l].q.empty() && !T[r].q.empty())
 64             T[x].ans = max(T[x].ans, T[l].q.top().dis + T[r].q.top().dis + T[x].mid);
 65     }
 66 }
 67 void getsize(int x,int fa,int dis){
 68     sz[x] = 1;
 69     add1(x,p,dis);
 70     if(col[x] == 0) T[p].q.push((D){x,dis});
 71     for(int i = last[x][1]; i; i = e[i][1].last)
 72         if(e[i][1].t != fa && !vis[i]){
 73             getsize(e[i][1].t, x, dis + e[i][1].w);
 74             sz[x] += sz[e[i][1].t];
 75         }
 76 }
 77 void getmid(int x,int id){
 78     int Max = max(sz[x], node - sz[x]);
 79     if(tmax > Max) tmax = Max, mid = id;
 80     for(int i = last[x][1]; i; i = e[i][1].last)
 81         if(!vis[i] && i != id && i != (id^1)) getmid(e[i][1].t, i);
 82 }
 83 void work(int tp,int x){
 84     p = tp;
 85     getsize(x,0,0);
 86     tmax = inf; node = sz[x]; getmid(x,mid = 0);
 87     vis[mid] = vis[mid^1] = 1;
 88     if(mid){
 89         int l = e[mid][1].t, r = e[mid^1][1].t;
 90         T[tp].mid = e[mid][1].w;
 91         work(T[tp].l = ++cnt, l);
 92         work(T[tp].r = ++cnt, r);
 93     }
 94     pushup(tp);
 95 }
 96 void solve(){
 97     int Q = getint(),x;
 98     char ch;
 99     while(Q--){
100         scanf("%c
",&ch);
101         if(ch == 'A'){
102             if(T[1].ans >= 0) printf("%d
",T[1].ans);
103             else printf("They have disappeared.
");
104         }
105         else{
106             x = getint();
107             col[x] ^= 1;
108             for(int i = last[x][2]; i; i = e[i][2].last){
109                 if(col[x] == 0)T[e[i][2].t].q.push((D){x,e[i][2].w});
110                 pushup(e[i][2].t);
111             }                
112         }
113     }
114 }
115 int main()
116 {
117     freopen("qtree.in","r",stdin);
118     freopen("qtree.out","w",stdout);
119     img = n = getint();
120     for(int i = 1; i < n; ++i){
121         int u = getint(), v = getint(), w = getint();
122         add(u,v,w);
123     }
124     ext = 1; rebuild(1,0);
125     ext = 2; work(cnt = 1, 1);
126     solve();
127     return 0;
128 }

View Code