Fork me on GitHub

「POJ-3237」Tree

发表于 | 分类于
字数统计: 1,555字 | 阅读时长 ≈ 10分钟

POJ-3237

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 b with 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

1
2
3
4
5
6
7
8
1
3
1 2 1
2 3 2
QUERY 1 2
CHANGE 1 3
QUERY 1 2
DONE

Sample Output

1
2
1
3

树剖码农题,是真的难调.

似乎for (int i = head[u]; ~i; i = E[i].next)和for (int i = head[u]; i; i = E[i].next)

有差别?

坑了我好久啊…

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
//my vegetable has exploded. :(
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<queue>
#include<climits>

#define max(x,y) (x>y?x:y)
#define min(x,y) (x<y?x:y)
#define MM(x,y) memset(x,y,sizeof(x))
#define MCPY(a,b) memcpy(a,b,sizeof(b))
#define pb push_back
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=b;i>=a;i--)
#define fi first
#define se second
#define int long long
using namespace std;

#define lc o<<1
#define rc o<<1|1
inline int quickpow(int m,int n,int p){int b=1;while(n){if(n&1)b=b*m%p;n=n>>1;m=m*m%p;}return b;}
inline int getinv(int x,int p){return quickpow(x,p-2,p);}
inline int read(void){
	int x=0,f=1;char ch=getchar();
	while(!isdigit(ch)){f=ch=='-'?-1:1;ch=getchar();}
	while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
	return x * f;
}
const int MAXN = 21000+10;
struct Edges{
    int to,w,next;
}E[MAXN<<2];
int cnt=0,dfs_cnt=0;
struct SegmentTree{
	int L,R,rev;
	int minn,maxx;
}tree[MAXN<<3];
int fa[MAXN],sz[MAXN],hson[MAXN],dep[MAXN],top[MAXN],dfn[MAXN],head[MAXN],T,n,uu[MAXN],vv[MAXN],ww[MAXN];
int R1[MAXN],R[MAXN];//映射
void addedge(int u,int v,int w){
    E[++cnt].to = v;
    E[cnt].w = w;
    E[cnt].next = head[u];
    head[u]=cnt;
}
inline void Reset(void){
    MM(hson,-1);MM(sz,0);MM(head,0);
    cnt=dfs_cnt=0;
}
///------------------head------------------
/*
void dfs1(int u,int F,int depth){
	printf("%d %d %d\n",u,F,depth);
    sz[u]=1;fa[u]=F;dep[u]=depth;
    for(int i=head[u]; i; i=E[i].next)
    {
        int v = E[i].to;
        if (v != F) {
			R[v]=E[i].w;
            dfs1(v,u,depth+1);
            sz[u] += sz[v];
            if((hson[u] == -1) || sz[hson[u]] < sz[v]) hson[u] = v;
        }
    }
}
*/
void dfs1(int u, int father, int depth) {
    dep[u] = depth;
    fa[u] = father;
    sz[u] = 1;
    for (int i = head[u]; i; i = E[i].next) {
        int v = E[i].to;
        if (v != fa[u]) {
            R[v] = E[i].w;
            dfs1(v, u, depth + 1);
            sz[u] += sz[v];
            if (hson[u] == -1 || sz[v] > sz[hson[u]]) hson[u] = v;
        }
    }
}
void dfs2(int u,int t){
	dfn[u] = dfs_cnt++; top[u] = t; R1[dfn[u]] = R[u];
	if (!hson[u]) return ;
	dfs2(hson[u],t);
	for (int i = head[u]; i; i = E[i].next){
		int v = E[i].to;
		if (v != fa[u] && v != hson[u]) dfs2(v,v);
	}
}
void pushup(int o){
	tree[o].minn = min(tree[lc].minn,tree[rc].minn);
	tree[o].maxx = max(tree[lc].maxx,tree[rc].maxx);
}
void Modify(int o){
	swap(tree[o].minn,tree[o].maxx);
	tree[o].maxx *= -1;
	tree[o].minn *= -1;
}
void pushdown(int o){
	if (!tree[o].rev) return ;
	tree[lc].rev ^= 1; tree[rc].rev ^= 1; //下放反转标记
	Modify(lc); Modify(rc);
	tree[o].rev = 0;
}
void Build(int o,int l,int r){
	tree[o].L = l,tree[o].R = r;
	tree[o].rev = 0;
	int m = (l + r) >> 1;
	if (l == r) tree[o].minn = tree[o].maxx = R1[l];
	else
	{
		Build(lc,l,m);
		Build(rc,m+1,r);
		pushup(o);
	}
}
void update(int o,int p,int z){
	if (p == tree[o].L && p == tree[o].R) {tree[o].minn = tree[o].maxx = z;}
	else
	{
		pushdown(o);
		int ll = tree[o].L,rr = tree[o].R,mid = (ll + rr) >> 1;
		if (p <= mid) update(lc,p,z);
			else update(rc,p,z);
		pushup(o);
	}
}
void update2(int o,int l,int r	){
	int L = tree[o].L,R = tree[o].R;
	if (L >= l && R <= r){
		tree[o].rev ^= 1;
		Modify(o);
		return ;
	}
	pushdown(o);
	int m = (L + R) >> 1;
	if (l <= m) update2(lc,l,r);
	if (r > m) update2(rc,l,r);
	pushup(o);
}
void Maintain(int u,int v){
	int topu = top[u],topv = top[v];
	while(topu != topv) {
		if (dep[topu] < dep[topv]) swap(u,v),swap(topu,topv);
		update2(1,dfn[topu],dfn[u]);
		u = fa[topu],topu = top[u];
	}
	if (u == v) return ;
	if (dep[u] < dep[v]) swap(u,v);
	update2(1,dfn[v] + 1,dfn[u]);
}
int query_on_tree(int o,int l,int r){
	int L = tree[o].L,R = tree[o].R;
	if (l <= L && R <= r) return tree[o].maxx;
	if (l > R || r < L) return -INT_MAX;
	pushdown(o);
	return max(query_on_tree(lc,l,r),query_on_tree(rc,l,r));
}
int Query_mx(int u,int v){
	if (u == v) return 0;
	int ans = -INT_MAX;
	int topu = top[u],topv = top[v];
	while(topu != topv) {
		if (dep[topu] < dep[topv]) swap(u,v),swap(topu,topv);
		ans = max(ans,query_on_tree(1,dfn[topu],dfn[u]));
		u = fa[topu],topu = top[u];
	}
	if (u == v) return ans;
	if (dep[u] < dep[v]) swap(u,v);
	return ans = max(ans,query_on_tree(1,dfn[v]+1,dfn[u]));
}
signed main(signed argc, char *argv[]){
    T=read();
	while(T--){
		Reset();
		n = read();
		rep(i,1,n-1){uu[i]=read(),vv[i]=read(),ww[i]=read();addedge(uu[i],vv[i],ww[i]);addedge(vv[i],uu[i],ww[i]);}
		/*
		for (int u = 1; u <= n; u++){
			for (int i = head[u]; i; i = E[i].next)
			printf("%d -> %d = %d\n",u,E[i].to,E[i].w);
			puts("");
		}
		*/
		dfs1(1,0,1);
		dfs2(1,1);
		Build(1,1,n);
		string op;
		while(cin >> op){
			if (op == "DONE") break;
			else if (op == "QUERY"){
				int u=read(),v=read();
				printf("%lld\n",Query_mx(u,v));
			}
			else if (op == "CHANGE"){
				int m=read(),newv=read();
				if (dep[uu[m]] < dep[vv[m]]) swap(uu[m],vv[m]);
				update(1,dfn[uu[m]],newv);
			}
			else
			{
				int u=read(),v=read();
				Maintain(u,v);
			}
		}
	}
	return 0;
}

/* Examples: */
/*IN
1

3
1 2 1
2 3 2
QUERY 1 2
CHANGE 1 3
QUERY 1 2
DONE
*/

/*OUT
1
3
*/