Codeforces 191C Fools and Roads

問題

無向木が与えられる。
この木上を、m個の出発点とゴールの組(ui, vi)について、
uiから一人が出発し、viへゴールする。

それぞれの辺について、合計何人が通るか求めよ。

制約条件

n≦10^5
m≦10^5

方針

累積和するだけ。
まずは木の根をどれか定める。

そしたら、num[u[i]], num[v[i]]に1を足して、
u, vのlcaのnumから2を引く。
それで累積和を、木の葉のほうから根のほうに向かって求めればいい。
これは再帰で出来る。

ソースコード

const int MX = 100010;
const int MX_L=17;

int n, ans[MX], num[MX];
int parent[MX_L][MX];
int depth[MX];
vector<vi> e, id;

void dfs(int c, int p, int d){
	depth[c] = d;
	parent[0][c] = p;
	rep(i, e[c].size()){
		int to = e[c][i];
		if(to == p) continue;
		dfs(to, c, d + 1);
	}
}
inline int lca(int a, int b){
	if(depth[a] > depth[b]) swap(a, b);
	int d = depth[b] - depth[a];
	rep(i, MX_L) if(d & 1 << i) b = parent[i][b];
	if(a == b) return a;
	for(int i = MX_L - 1; i >= 0; i--) if(parent[i][a] != parent[i][b]){
		a = parent[i][a];
		b = parent[i][b];
	}
	return parent[0][a];
}

void rec(int c, int p){
	rep(i, e[c].size()) if(e[c][i] != p){
		rec(e[c][i], c);
		ans[id[c][i]] += num[e[c][i]];
		num[c] += num[e[c][i]];
	}
}

int main()
{
	cin >> n;
	e.resize(n);
	id.resize(n);
	rep(i, n - 1){
		int a, b;
		cin >> a >> b;
		a--; b--;
		e[a].pb(b); e[b].pb(a);
		id[a].pb(i); id[b].pb(i);
	}
	
	//n for dummy root
	parent[0][n] = n;
	dfs(0, n, 1);
	rep(i, MX_L - 1) rep(j, n) parent[i + 1][j] = parent[i][parent[i][j]];
	
	int m;
	cin >> m;
	while(m--){
		int a, b;
		cin >> a >> b;
		a--; b--;
		int u = lca(a, b);
		num[a]++; num[b]++; num[u] -= 2;
	}
	rec(0, 0);
	assert(num[0] == 0);
	
	rep(i, n - 1) cout << ans[i] << " ";
	cout << endl;
	
	return 0;
}