> 树链剖分……
> 提供我的对拍程序：
> #include<cstdio>
> #include<cstdlib>
> #include<cstring>
> #include<ctime>
> 
> using namespace std;
> 
> FILE *fin, *fout;
> 
> const int n = 1000, m = 4000;
> 
> int adj[n + 5][n + 5];
> int ex[n + 5], ey[n + 5];
> int fat[n + 5], num[n + 5], last[n + 5], ans;
> int vis[n + 5];
> 
> int find(int x)
> {
> 	if (fat[x] != x) fat[x] = find(fat[x]); return fat[x];
> }
> 
> void dfs(int t, int u)
> {
> 	last[t] = u;
> 	for (int i = 1; i <= n; i++)
> 		if (adj[t][i] != 0 && i != u) dfs(i, t);
> }
> 
> int lca(int x, int y)
> {
> 	for (int i = 1; i <= n; i++) vis[i] = 0;
> 	while (x){
> 		vis[x] = 1; x = last[x];
> 	}
> 	while (!vis[y]) y = last[y];
> 	return y;
> }
> 
> void tree_change(int t, int u)
> {
> 	while (t != u){
> 		adj[t][last[t]] = adj[last[t]][t] = -adj[t][last[t]]; t = last[t];
> 	}
> }
> 
> void tree_calc(int t, int u)
> {
> 	while (t != u){
> 		if (adj[last[t]][t] > ans) ans = adj[last[t]][t];
> 		t = last[t];
> 	}
> }
> 
> int main()
> {
> 	fin = fopen("tree.in", "w");
> 	fout = fopen("force.out", "w");
> 	int i, u, v, c, j, k;
> 	fprintf(fin, "10\n"); 
> 	for (int w = 1; w <= 10; w++){
> 		memset(adj, 0, sizeof(adj));
> 		memset(last, 0, sizeof(last));
> 		memset(fat, 0, sizeof(fat));
> 		memset(ex, 0, sizeof(ex));
> 		memset(ey, 0, sizeof(ey));
> 		memset(num, 0, sizeof(num));
> 		memset(vis, 0, sizeof(vis));						
> 		fprintf(fin, "%d\n", n);
> 		for (i = 1; i <= n; i++) fat[i] = i;
> 		srand(time(0));
> 		for (i = 1; i < n; i++)
> 			while (1){
> 				u = rand() % n + 1; v = rand() % n + 1; 
> 				if (find(u) == find(v)) continue; c = rand() - rand(); if (c == 0) c++;
> 				fat[find(v)] = fat[u]; adj[u][v] = adj[v][u] = c; ex[i] = u; ey[i] = v;
> 				fprintf(fin, "%d %d %d\n", u, v, c); break;
> 			}
> 		dfs(1, 0);
> 		for (i = 1; i <= m; i++){
> 			k = rand() % 4;
> 			if (k == 0){
> 				u = rand() % (n - 1) + 1; c = rand() - rand(); if (c == 0) c++;
> 				fprintf(fin, "CHANGE %d %d\n", u, c); adj[ex[u]][ey[u]] = adj[ey[u]][ex[u]] = c;
> 			} else if (k == 1){
> 				u = rand() % n + 1; v = rand() % n + 1; 
> 				while (u == v) v = rand() % n + 1; j = lca(u, v);
> 				fprintf(fin, "NEGATE %d %d\n", u, v); 
> 				tree_change(u, j); tree_change(v, j);
> 			} else {
> 				u = rand() % n + 1; v = rand() % n + 1;
> 				while (u == v) v = rand() % n + 1;	 j = lca(u, v);
> 				fprintf(fin, "QUERY %d %d\n", u, v); ans = 1 << 30; ans = -ans;
> 				tree_calc(u, j); tree_calc(v, j);
> 				fprintf(fout, "%d\n", ans);
> 			}
> 		}
> 		fprintf(fin, "DONE\n");
> 	}
> 	fclose(fin); fclose(fout);
> 	return 0;
> }
> 另外问一句，最多多少次操作呀？题目貌似没有说……


历尽艰辛，反复调试，终于AC！
感激不尽！！