代码

#include<bits/stdc++.h>
#define nb 10
using namespace std;

int n, N, R, w[nb];
int dep[nb], fa[nb], size[nb], son[nb];
int cnt, id[nb], wnew[nb], top[nb];
vector<int> G[nb];

void dfs1(int u, int f, int deep){
	fa[u] = f;
	dep[u] = deep;
	size[u] = 1;
	int maxson = -1;
	for(int i = 0; i < G[u].size(); i++){
		int v = G[u][i];
		if(v == f){
			continue;
		}
		dfs1(v, u, deep + 1);
		size[u] += size[v];
		if(size[v] > maxson){
			maxson = size[v];
			son[u] = v;
		}
	}
}

void dfs2(int u, int topf){
	id[u] = ++cnt;
	wnew[cnt] = w[u];
	top[u] = topf;
	if(!son[u]){
		return;
	}
	dfs2(son[u], topf);
	for(int i = 0; i < G[u].size(); i++){
		int v = G[u][i];
		if(v == fa[u] || v == son[u]){
			continue;
		}
		dfs2(v, v);
	}
}

struct node{
	int l, r, sum, f;
}tree[nb << 2];

void build(int k, int l, int r){
	tree[k].l = l;
	tree[k].r = r;
	tree[k].sum = tree[k].f = 0;
	if(l == r){
		tree[k].sum = wnew[l];
		return;
	}
	int mid = (l + r) >> 1;
	build(k << 1, l, mid);
	build(k << 1 | 1, mid + 1, r);
	tree[k].sum = tree[k << 1].sum + tree[k << 1 | 1].sum;
}

void down(int k){
	tree[k << 1].sum += (tree[k << 1].r - tree[k << 1].l + 1) * tree[k].f;
	tree[k << 1 | 1].sum += (tree[k << 1 | 1].r - tree[k << 1 | 1].l + 1) * tree[k].f;
	tree[k << 1].f += tree[k].f;
	tree[k << 1 | 1].f += tree[k].f;
	tree[k].f = 0;
}

int query(int k, int a, int b){
	if(tree[k].l >= a && tree[k].r <= b){
		return tree[k].sum;
	}
	if(tree[k].f){
		down(k);
	}
	int mid = (tree[k].l + tree[k].r) >> 1, ans = 0;
	if(a <= mid){
		ans += query(k << 1, a, b);
	}
	if(b > mid){
		ans += query(k << 1 | 1, a, b);
	}
	return ans;
}

void add(int k, int a, int b, int val){
	if(tree[k].l >= a && tree[k].r <= b){
		tree[k].sum += (tree[k].r - tree[k].l + 1) * val;
		tree[k].f += val;
		return;
	}
	if(tree[k].f){
		down(k);
	}
	int mid = (tree[k].l + tree[k].r) >> 1;
	if(a <= mid){
		add(k << 1, a, b, val);
	}
	if(b > mid){
		add(k << 1 | 1, a, b, val);
	}
	tree[k].sum = tree[k << 1].sum + tree[k << 1 | 1].sum;
}

int chainquery(int x, int y){
	int ans = 0;
	while(top[x] != top[y]){
		if(dep[top[x]] < dep[top[y]]){
			swap(x, y);
		}
		ans += query(1, id[top[x]], id[x]);
		x = fa[top[x]];
	}
	if(dep[x] > dep[y]){
		swap(x, y);
	}
	ans += query(1, id[x], id[y]);
	return ans;
}

void chainadd(int x, int y, int val){
	while(top[x] != top[y]){
		if(dep[top[x]] < dep[top[y]]){
			swap(x, y);
		}
		add(1, id[top[x]], id[x], val);
		x = fa[top[x]];
	}
	if(dep[x] > dep[y]){
		swap(x, y);
	}
	add(1, id[x], id[y], val);
	return;
}

int main(){
	N = 2;
	R = 1;
	G[1].push_back(2);
	G[2].push_back(1);
	dfs1(R, 0, 1);
	dfs2(R, R);
	build(1, 1, N);
	cin >> n;
	while(n--){
		int a, b;
		cin >> a >> b;
		chainadd(1, 1, a);
		chainadd(1, 1, b);
		cout << chainquery(1, 2) << endl;
		chainadd(1, 1, -a);
		chainadd(1, 1, -b);
	}
	return 0;
}

评测结果