洛谷P1600 天天爱跑步(差分 LCA 桶)

题意

题目链接

Sol

一步一步的来考虑

\\(25 \\%\\)：直接\\(O(nm)\\)的暴力

链的情况：维护两个差分数组，分别表示从左向右和从右向左的贡献，

\\(S_i = 1\\)：统计每个点的子树内有多少起点即可

\\(T_i = 1\\)：同样还是差分的思想，由于每个点 能对其产生的点的深度是相同的(假设为\\(x\\))，那么访问该点时记录下\\(dep[x]\\)的数量，将结束时\\(dep[x]\\)的数量与其做差即可

满分做法和上面类似，我们考虑把每个点的贡献都转换到子树内统计

对于每次询问，拆为\\(S->lca, lca -> T\\)两种(从下到上 / 从上到下)

从上往下需要满足的条件：\\(dep[i] - w[i] = dep[T] - len\\)

从下往上需要满足的条件：\\(dep[i] + w[i] = dep[s]\\)

#include<bits/stdc++.h>
#define Pair pair<int, int>
#define MP make_pair
#define fi first
#define se second 
using namespace std;
const int MAXN = 1e6 + 10, mod = 1e9 + 7, B = 20;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < \'0\' || c > \'9\') {if(c == \'-\') f = -1; c = getchar();}
    while(c >= \'0\' && c <= \'9\') x = x * 10 + c - \'0\', c = getchar();
    return x * f;
}
int N, M, ans[MAXN], dep[MAXN], top[MAXN], son[MAXN], siz[MAXN], fa[MAXN], S[MAXN], 
          T[MAXN], w[MAXN], tmp[MAXN], num2[MAXN], sum1[MAXN], sum2[MAXN], Lca[MAXN];
int *num1;//上 -> 下 
vector<int> up[MAXN], da[MAXN], dc[MAXN];
vector<int> v[MAXN];
void dfs(int x, int _fa) {
    dep[x] = dep[_fa] + 1; siz[x] = 1; fa[x] = _fa;
    for(int i = 0, to; i < v[x].size(); i++) {
        if((to = v[x][i]) == _fa) continue;
        dfs(to, x);
        siz[x] += siz[to];
        if(siz[to] > siz[son[x]]) son[x] = to;
    }
}
void dfs2(int x, int topf) {
    top[x] = topf;
    if(!son[x]) return ;
    dfs2(son[x], topf);
    for(int i = 0, to; i < v[x].size(); i++) 
        if(!top[to = v[x][i]]) dfs2(to, to);
}
int LCA(int x, int y) {
    while(top[x] ^ top[y]) {
        if(dep[top[x]] < dep[top[y]]) swap(x, y);
        x = fa[top[x]];
    }
    return dep[x] < dep[y] ? x : y;
}
void Deal(int s, int t, int id) {// from s to t
    int lca = LCA(s, t); Lca[id] = lca;
    up[lca].push_back(s);//from down to up
    int dis = dep[s] + dep[t] - 2 * dep[lca];
    sum2[s]++;
    da[t].push_back(dep[t] - dis);//increase
    dc[lca].push_back(dep[t] - dis);//decrase
}
void Find(int x) {
    int t1 = num1[dep[x] - w[x]], t2 = num2[dep[x] + w[x]];// 1: 从上往下   2：从下往上 
    for(int i = 0, to; i < v[x].size(); i++) {
        if((to = v[x][i]) == fa[x]) continue;
        Find(to);
    }
    num2[dep[x]] += sum2[x];
    for(int i = 0; i < da[x].size(); i++) num1[da[x][i]]++;
    ans[x] += num2[dep[x] + w[x]] - t2 + num1[dep[x] - w[x]] - t1;
    for(int i = 0; i < up[x].size(); i++) num2[dep[up[x][i]]]--;
    for(int i = 0; i < dc[x].size(); i++) num1[dc[x][i]]--;
}
int main() {
    //freopen(\"a.in\", \"r\", stdin); freopen(\"a.out\", \"w\", stdout);
    num1 = tmp + (int)3e5 + 10;
    N = read(); M = read();
    for(int i = 1; i <= N - 1; i++) {
        int x = read(), y = read();
        v[x].push_back(y); v[y].push_back(x);
    }
    dep[0] = -1; dfs(1, 0); dfs2(1, 1);
    //for(int i = 1; i <= N; i++, puts(\"\")) for(int j = 1; j <= N; j++) printf(\"%d %d %d\\n\", i, j, LCA(i, j));  
    for(int i = 1; i <= N; i++) w[i] = read();
    for(int i = 1; i <= M; i++) S[i] = read(), T[i] = read(), Deal(S[i], T[i], i);
    Find(1);
    for(int i = 1; i <= M; i++) if(dep[S[i]] - dep[Lca[i]] == w[Lca[i]]) ans[Lca[i]]--;
    for(int i = 1; i <= N; i++) printf(\"%d \", ans[i]);
    return 0;
}