LINK https://loj.ac/problem/2359
思路
首先发现如果对于一个节点, 假设一个节点需要统计从字数内来的贡献
需要满足 \(dep_u - dep_s = w_u\)
这个条件其实可以转化成 \(dep_u - w_u = dep_s\)
然后对于这个东西我们只需要记录下 \(dep_s\) 的信息就好了
然后考虑差分, 把一个询问先分解成 \(s->lca\) 和 \(lca->t\) 两部分
接着把连边分别差分处理就可以了
从子树以外的地方的贡献也很好维护
- //Author: dream_maker
- #include<bits/stdc++.h>
- using namespace std;
- //----------------------------------------------
- //typename
- typedef long long ll;
- //convenient for
- #define fu(a, b, c) for (int a = b; a <= c; ++a)
- #define fd(a, b, c) for (int a = b; a>= c; --a)
- #define fv(a, b) for (int a = 0; a <(signed)b.size(); ++a)
- //inf of different typename
- const int INF_of_int = 1e9;
- const ll INF_of_ll = 1e18;
- //fast read and write
- template <typename T>
- void Read(T &x) {
- bool w = 1;x = 0;
- char c = getchar();
- while (!isdigit(c) && c != '-') c = getchar();
- if (c == '-') w = 0, c = getchar();
- while (isdigit(c)) {
- x = (x<<1) + (x<<3) + c -'0';
- c = getchar();
- }
- if (!w) x = -x;
- }
- template <typename T>
- void Write(T x) {
- if (x <0) {
- putchar('-');
- x = -x;
- }
- if (x> 9) Write(x / 10);
- putchar(x % 10 + '0');
- }
- //----------------------------------------------
- const int N = 3e5;
- struct Node{
- int u, len, typ, dir;
- //typ 1:insert -1:erase
- //dir 1:up 0:down
- };
- vector<Node> g[N];
- struct Edge{
- int v, nxt;
- } E[N <<1];
- int head[N], tot = 0;
- int down[N << 1], up[N << 1];
- int Log[N], dep[N], w[N];
- int Fa[N][18];
- int n, m, ans[N];
- void add(int u, int v) {
- E[++tot] = (Edge) {v, head[u]};
- head[u] = tot;
- }
- void dfs(int u, int fa) {
- dep[u] = dep[fa] + 1;
- Fa[u][0] = fa;
- fu(i, 1, Log[dep[u]]) Fa[u][i] = Fa[Fa[u][i - 1]][i - 1];
- for (int i = head[u]; i; i = E[i].nxt) {
- int v = E[i].v;
- if (v == fa) continue;
- dfs(v, u);
- }
- }
- int Lca(int u, int v) {
- if (dep[u] < dep[v]) swap(u, v);
- int delta = dep[u] - dep[v];
- fu(i, 0, Log[delta])
- if ((delta>> i) & 1)
- u = Fa[u][i];
- if (u == v) return u;
- int k = Log[dep[u]];
- while (Fa[u][0] != Fa[v][0]) {
- if (Fa[u][k] != Fa[v][k]) {
- u = Fa[u][k];
- v = Fa[v][k];
- }
- k--;
- }
- return Fa[u][0];
- }
- void solve(int u) {
- ans[u] -= down[w[u] - dep[u] + N] + up[w[u] + dep[u]];
- fv(j, g[u]) {
- Node now = g[u][j];
- if (now.dir) up[now.len] += now.typ;
- else down[now.len] += now.typ;
- }
- for (int i = head[u]; i; i = E[i].nxt) {
- int v = E[i].v;
- if (v == Fa[u][0]) continue;
- solve(v);
- }
- ans[u] += down[w[u] - dep[u] + N] + up[w[u] + dep[u]];
- }
- int main() {
- #ifdef dream_maker
- freopen("input.txt", "r", stdin);
- #endif
- Read(n), Read(m);
- Log[1] = 0; fu(i, 2, n) Log[i] = Log[i>> 1] + 1;
- fu(i, 2, n) {
- int u, v;
- Read(u), Read(v);
- add(u, v);
- add(v, u);
- }
- dfs(1,0);
- fu(i, 1, n) Read(w[i]);
- fu(i, 1, m) {
- int u, v;
- Read(u), Read(v);
- int lca = Lca(u, v);
- g[u].push_back((Node){u, dep[u], 1, 1});
- g[Fa[lca][0]].push_back((Node){Fa[lca][0], dep[u], -1, 1});
- g[v].push_back((Node){v, dep[u] - 2 * dep[lca] + N, 1, 0});
- g[lca].push_back((Node){lca, dep[u] - 2 * dep[lca] + N, -1, 0});
- }
- solve(1);
- fu(i, 1, n) {
- Write(ans[i]);
- putchar(' ');
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2806231.html