这是NOIP2016D1T2？我觉得我参加NOIP绝对爆零。

$\texttt{Description}$

由于题面太长，不再赘述。传送门

$\texttt{Solution}$

手动膜你每个玩家的跑步过程显然不可行，因此只能对于每个观察员计算有多少个玩家会对他产生贡献。

考虑一个玩家，它会先从 $s$ 跑到 $s$ 和 $t$ 的 $lca$ 上，因此分两种情况。

一、 $u$ 在某个玩家 $s$ 到 $lca$ 的路径上。

那么此时玩家到 $u$ 的时刻应为 $Dep_s-Dep_u$，$Dep_u$ 表示 $u$ 的深度。

当 $Dep_s-Dep_u=w_u$ 时，这个玩家对 $u$ 产生贡献。我们希望把与 $u$ 无关的项全部移到一边去，因此移项得 $Dep_s=Dep_u+w_u$。

二、 $u$ 在某个玩家从 $lca$ 到 $t$ 的路径上。

那么此时玩家到 $u$ 的时刻应为 $Dep_s-Dep_{lca}+Dep_u-Dep_{lca}$。当 $Dep_s+Dep_u-Dep_{lca}\times 2=w_u$ 时产生贡献，移项得 $Dep_s+-Dep_{lca}\times 2=w_u-Dep_u$。

以上两种情况，均要求 $s$ 或 $t$ 是 $u$ 的子节点，且 $u$ 是 $lca$ 的子节点。可以想到线段树合并，对每个节点建立两颗线段树，一个维护情况一的贡献，一个维护情况二的贡献。查询情况一的线段树里面下标为 $Dep_u+w_u$ 的值即可。情况二同理。由于 $u$ 在 $lca$ 时会重复计算，因此需要将 $lca$ 与它的父亲减一下。感觉这里光凭说有点绕，详见代码。

时间复杂度 $O(nlogn)$。

//这题的权值线段树只需要单点修改单点查询，但是需要合并，使用vector应该能够做到更好的复杂度，但是我懒（逃
#include <cstdio>
#include <cmath>
#include <vector>

std::vector<int> sons[300005];
int w[300005], fa[300005][19], Dep[300005], ans[300005], n;
void dfs(const int u) {
	int MAX(ceil(log2(Dep[u] = Dep[fa[u][0]] + 1)));
	for (int i(1); i <= MAX; ++ i) fa[u][i] = fa[fa[u][i - 1]][i - 1];
	for (int v : sons[u])
		if (v != fa[u][0]) fa[v][0] = u, dfs(v);
}
int LCA(int u, int v) {
	if (Dep[u] < Dep[v]) u ^= v ^= u ^= v;
	int MAX(ceil(log2(Dep[u] - Dep[v])));
	for (int i(0); i <= MAX; ++ i)
		if (Dep[u] - Dep[v] & 1 << i) u = fa[u][i];
	if (u == v) return u;
	for (int i(ceil(log2(Dep[u]))); i >= 0; -- i)
		if (fa[u][i] != fa[v][i]) u = fa[u][i], v = fa[v][i];
	return fa[u][0];
}

int sum[10000005], ls[10000005], rs[10000005], root[300005], root2[300005], tot;
void update(int& O, const int l, const int r, const int p, const int d) {
	if (!O) O = ++ tot;
	sum[O] += d;
	if (l == r) return;
	const int mid(l + r >> 1);
	if (p <= mid) update(ls[O], l, mid, p, d);
	else update(rs[O], mid + 1, r, p, d);
}
void merge(int &x, const int y, const int l, const int r) {
	if (!x || !y) {x |= y; return;}
	sum[x] += sum[y];
	if (l == r) return;
	const int mid(l + r >> 1);
	merge(ls[x], ls[y], l, mid);
	merge(rs[x], rs[y], mid + 1, r);
}
int query(const int O, const int l, const int r, const int p) {
	if (!O || p < l || r < p) return 0;//有可能出现dep[u]+w[u]>n的情况，因此特判一下。
 	if (l == r) return sum[O];
	const int mid(l + r >> 1);
	if (p <= mid) return query(ls[O], l, mid, p);
	else return query(rs[O], mid + 1, r, p);
}

void dfs2(const int u) {
	for (int v : sons[u]) if (v != fa[u][0]) {
		dfs2(v);
		merge(root[u], root[v], -n, n);
		merge(root2[u], root2[v], -n, n);
	}
	ans[u] = query(root2[u], 1, n << 1, n + w[u] - Dep[u]) + query(root[u], 1, n << 1, n + Dep[u] + w[u]);
}

int main() {
	int m;
	scanf("%d%d", &n, &m);
	for (int i(1); i < n; ++ i) {
		int u, v;
		scanf("%d%d", &u, &v);
		sons[u].push_back(v), sons[v].push_back(u);
	}
	dfs(1);
	for (int i(1); i <= n; ++ i) scanf("%d", w + i);
	for (int i(1); i <= m; ++ i) {
		int s, t, lca;
		scanf("%d%d", &s, &t);
		lca = LCA(s, t);
		update(root[s], 1, n << 1, n + Dep[s], 1);//本题的核心，套式子，算贡献
		update(root2[t], 1, n << 1, n + Dep[s] - Dep[lca] * 2, 1);
		update(root[lca], 1, n << 1, n + Dep[s], -1);
		update(root2[fa[lca][0]], 1, n << 1, n + Dep[s] - Dep[lca] * 2, -1);
	}
	dfs2(1);
	for (int i(1); i <= n; ++ i)
		printf("%d ", ans[i]);
	return 0;
}

zqs`s blog

题解【P1600 [NOIP2016 提高组] 天天爱跑步】

$\texttt{Description}$

$\texttt{Solution}$