Colorful Tree [AtCoder Beginner Contest 133 F]

https://atcoder.jp/contests/abc133/tasks/abc133_f

前提知識

• LCA
• クエリ先読み

解説

https://atcoder.jp/contests/abc133/submissions/6312857

重要なこととして、制約を簡単にした問題が解けないか考えてみる。
今回で言うと、辺の長さの変更が難しいので、これを抜いてみる。
すると、木の2頂点の距離となる。
これはLCAを使えば解ける。
これを発展させて解いていこう。
LCAを使った典型テクとして、「dist(根,a) + dist(根,b) - 2*dist(根,lca(a,b))」があり、今回もこれをつかう。
これで問題は以下のように言い換えることができた。
　
根から頂点uの間で、条件のように辺の長さを変更した後の距離は？
この答えは以下の式で得ることができる。
(根からuまでの距離) - (根からuまでで色がxの辺の総和) + (根からuまでの色がxの本数) * y
ここからが経験ブレイクスルーなのだが、『クエリ先読み』を使おう。
根から以下の配列を更新しながら、dfsすることで、その頂点での(根からuまでで色がxの辺の総和)と(根からuまでの色がxの本数)がわかる。
tot[col] := 色colの辺の長さの総和
cnt[col] := 色colの辺の本数
クエリ先読みを使って、ある頂点で、計算するべきクエリの計算を行うことで、ならし計算量が間に合う。

int N, Q;
vector<vector<int>> E[101010];   // {to, color, len}
vector<vector<int>> que[101010]; // {que, color, len, delta}
ll ans[101010];
//---------------------------------------------------------------------------------------------------
ll tot[101010];
ll cnt[101010];
void dfs(int cu, int pa, ll sm) {
	fore(v, que[cu]) {
		int q = v[0], col = v[1], len = v[2], delta = v[3];
		ans[q] += (sm - tot[col] + 1LL * cnt[col] * len) * delta;
	}

	fore(v, E[cu]) {
		int to = v[0], col = v[1], len = v[2];
		if (to == pa) continue;
		tot[col] += len;
		cnt[col]++;
		dfs(to, cu, sm + len);
		tot[col] -= len;
		cnt[col]--;
	}
}
//---------------------------------------------------------------------------------------------------
void _main() {
	cin >> N >> Q;

	HLDecomposition hld;
	hld.init(N);

	rep(i, 0, N - 1) {
		int a, b, c, d;
		cin >> a >> b >> c >> d;
		a--; b--;
		E[a].push_back({ b,c,d });
		E[b].push_back({ a,c,d });

		hld.add(a, b);
	}

	hld.build();

	rep(i, 0, Q) {
		int x, y, u, v; cin >> x >> y >> u >> v;
		u--; v--;

		que[u].push_back({ i, x, y, 1 });
		que[v].push_back({ i, x, y, 1 });
		que[hld.lca(u, v)].push_back({ i, x, y, -2 });
	}

	dfs(0, -1, 0);

	rep(i, 0, Q) printf("%lld\n", ans[i]);
}