[NOIp2016]天天爱跑步

Description

BZOJ4719
Luogu1600
给定一棵树和若干玩家，玩家在树上的路径中跑，移动速度为(1mbox{边}/s)。求某一时刻经过某个点的玩家个数。

Solution

这个题由于比较难，我们要看部分分做题。

Part 1

测试点1，2，3，4。
起点等于终点或(w_i=0)，这种点就直接讨论一下水过去就行。

测试点5。
数据小，直接(O(n^2))暴力模拟也可以过。

Part 2

测试点6，7，8。
链上的情况比较复杂。
考虑哪些玩家(x)会对某个点(i)产生贡献，这需要满足起点在(i)一侧且(dis_{i,x} = w_i)，即(x=ipm w_i)，终点在(i)的另一侧。
我们可以借助差分的思想，从左向右和从右向左各扫一遍，扫到起点时将(ans_{S_i})自增，扫到终点时再减回来。这样扫到一个点时(ans_{ipm w_i})就是答案。

测试点9，10，11，12。
起点是1，只有(w_i=deep_i)的点才有答案，答案是子树中的玩家个数。

测试点13，14，15，16。
这次是终点为1了，和起点为1很像，只有(w_i + deep_i = S_j)且(S_j)在(i)的子树中的路径(j)会对点(i)有贡献，运用链上的想法，记录一下某个节点递归进入子树前后的(ans)的变化量即为该点答案。

Part 3

综合考虑Part 2中的思路。将路径拆分为向上和向下两部分，分别类比起点为1和终点为1时的情况求解。需要注意的是如果(lca)被一条路径贡献了两次，需要将多余的贡献删去。

Code

#include <cstdio>

const int N = 3e6 + 10;
const int M = 2*N + 10;

int n, m;
int hd[N], to[M], nxt[M], cnt;
int dis[N], w[N], sz[N], son[N], top[N], fa[N];
int S[N], T[N];
int ptot;
struct Path {
    int s, t, up, ns, nt;
} p[M];
int pret[M];
int uac[M], dac[M];
int ps[N], pt[N];
int mark[N], ans[N];

inline void adde(int x, int y) {
    cnt++; to[cnt] = y; nxt[cnt] = hd[x];
    hd[x] = cnt;
}

void dfs(int x, int f) {
	dis[x] = dis[f] + 1;
	fa[x] = f; sz[x] = 1;
    for (int i = hd[x]; i; i = nxt[i]) if (to[i] != f) {
        dfs(to[i], x);
        sz[x] += sz[to[i]];
        if (sz[son[x]] < sz[to[i]]) son[x] = to[i];
    }
}
void rebuild(int x, int f) {
    top[x] = f;
    if (son[x]) rebuild(son[x], f);
    for (int i = hd[x]; i; i = nxt[i]) if (to[i] != son[x] && to[i] != fa[x]) {
        rebuild(to[i], to[i]);
    }
} 

int lca(int x, int y) {
    while (top[x] != top[y]) {
        if (dis[fa[top[x]]] > dis[fa[top[y]]]) x = fa[top[x]];
        else y = fa[top[y]];
    }
    return dis[x] < dis[y] ? x : y;
}

void addp(int s, int t, int up) {
    ptot++;
    p[ptot].s = s; p[ptot].t = t; p[ptot].up = up;
    p[ptot].ns = ps[s]; ps[s] = ptot;
    p[ptot].nt = pt[t]; pt[t] = ptot;
}

void calc(int x, int f) {
    int uOld = uac[w[x]+dis[x]], dOld = dac[w[x]-dis[x]+n];
// 统计该点的贡献	
    for (int i = ps[x]; i; i = p[i].ns) 
		if (p[i].up) uac[dis[p[i].s]]++;
    for (int i = pt[x]; i; i = p[i].nt) 
		if (!p[i].up) dac[pret[i] - dis[p[i].s] + n]++;
// 递归计算后将差量作为答案		
    for (int i = hd[x]; i; i = nxt[i]) if (to[i] != f) calc(to[i], x);
    ans[x] = uac[w[x]+dis[x]] - uOld + dac[w[x]-dis[x]+n] - dOld - mark[x];
// 去掉不应继续上传的路径的贡献	
    for (int i = ps[x]; i; i = p[i].ns) 
		if (!p[i].up) dac[pret[i] - dis[p[i].s] + n]--;
    for (int i = pt[x]; i; i = p[i].nt) 
		if (p[i].up) uac[dis[p[i].s]]--;
}

int main() {
// 读入
	scanf("%d%d", &n, &m);
    for (int i = 1, x, y; i < n; ++i) {
        scanf("%d%d", &x, &y);
        adde(x, y);
        adde(y, x);
    }
    for (int i = 1; i <= n; ++i) scanf("%d", &w[i]);
    for (int i = 1; i <= m; ++i) {
        scanf("%d%d", &S[i], &T[i]);
    }
// 树剖求LCA	
	dfs(1, 0); rebuild(1, 1);
// 切分路径
    for (int i = 1; i <= m; ++i) {
        int Lca = lca(S[i], T[i]);
        if (Lca == S[i]) {
            addp(S[i], T[i], 0);
        } else if (Lca == T[i]) {
            addp(S[i], T[i], 1);
        } else {
            addp(S[i], Lca, 1);
            addp(Lca, T[i], 0);
            pret[ptot] = pret[ptot-1] = dis[S[i]] - dis[Lca];
            if (dis[S[i]] == w[Lca] + dis[Lca]) mark[Lca]++; // 去重
        }
    } 
// dfs计算	
    calc(1, 0);
	
	for (int i = 1; i <= n; ++i) printf("%d ", ans[i]); puts("");
	return 0;
}