树链剖分……
提供我的对拍程序：
#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;
}
另外问一句，最多多少次操作呀？题目貌似没有说……

• Re:260行代码……纪念我在POJ上提交过的最长的程序…… (10) 0803enjoy 2012-03-10 16:52:12
• Re:260行代码……纪念我在POJ上提交过的最长的程序…… (2739) PoPoQQQ 2014-06-06 17:39:58
• 260行叫代码？ (0) xindubawukong 2015-01-02 18:19:39