题目分析：

一年前还是个傻子的时候居然直接放弃了这题。

首先列出两个方程：如果i节点的观察员能够观察到由s->t的那个人，那么:

\[dep[s] - dep[i] = w[i], dep[t] - dep[i] = len - w[i]
\]

整理得到：$$dep[s] = w[i] + dep[i] (1), dep[t] - len = dep[i] - w[i] (2)$$

也就是说：只要起点满足方程(1)和终点满足方程(2)的都能被i看到，下面考虑下差分：因为树的dfs是连续的，所以以节点i为根节点的子树的答案就是：扫描子树后的 - 扫描子树前的，对于一个人从s->t，在s节点+dep[s]，在t节点+dep[t] - len，在lca节点-dep[s], 在fa[lca]节点-(dep[t] - len)（s+, t+, lca-, fa[lca]-，这样才能做到补充不漏，自行脑补），每次处理该点的差分标记更新cnt1和cnt2数组（cnt1表示关于起点的差分值的个数，cnt2表示关于终点的差分值的个数，对应上面的方程），节点i的答案就是:$$(扫描后的cnt1[w[i] + dep[i]] + 扫描后的cnt2[dep[i] - w[i]]) - (扫描前的cnt1[w[i] + dep[i]] + 扫描前的cnt2[dep[i] - w[i]])$$

最后还要注意cnt数组记录的差分值可能出现负数，所以要给作差的差分值+offset，来保证下标是合法的。

code

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

namespace IO{

    inline ll read(){

        ll i = 0, f = 1; char ch = getchar();

        for(; (ch < '0' || ch > '9') && ch != '-'; ch = getchar());

        if(ch == '-') f = -1, ch = getchar();

        for(; ch >= '0' && ch <= '9'; ch = getchar()) i = (i << 3) + (i << 1) + (ch - '0');

        return i * f;

    }

    inline void wr(ll x){

        if(x < 0) putchar('-'), x = -x;

        if(x > 9) wr(x / 10);

        putchar(x % 10 + '0');

    }

}using namespace IO;

const int N = 3e5 + 5, M = 3e5 + 5;

int n, m, ecnt, adj[N], nxt[M << 1], go[M << 1];

int cnt1[N * 3], cnt2[N * 3], w[N], offset;

int fa[N][25], dep[N], ans[N];

struct node{int type, val, flag;};

vector<node> tag[N];

inline void addEdge(int u, int v){nxt[++ecnt] = adj[u], adj[u] = ecnt, go[ecnt] = v;}

inline void pre(int u, int f){

    dep[u] = dep[f] + 1;

    fa[u][0] = f;

    for(int i = 1; i <= 20; i++) fa[u][i] = fa[fa[u][i - 1]][i - 1];

    for(int v, e = adj[u]; e; e = nxt[e]){

        if((v = go[e]) == f) continue;

        pre(v, u);

    }

}

inline int getLca(int u, int v){

    if(dep[u] < dep[v]) swap(u, v);

    int delta = dep[u] - dep[v];

    for(int i = 20; i >= 0; i--) if((1 << i) & delta) u = fa[u][i];

    if(u == v) return u;

    for(int i = 20; i >= 0; i--) if(fa[u][i] != fa[v][i]) u = fa[u][i], v = fa[v][i];

    return fa[u][0];

}

inline void addTag(int u, int v){

    int lca = getLca(u, v), len = dep[u] + dep[v] - 2 * dep[lca];

    tag[u].push_back((node){1, dep[u], 1}), tag[v].push_back((node){2, dep[v] - len + offset, 1});

    tag[lca].push_back((node){1, dep[u], -1}), tag[fa[lca][0]].push_back((node){2, dep[v] - len + offset, -1});

}

inline void dfs(int u, int f){

    int cur = cnt1[w[u] + dep[u]] + cnt2[dep[u] - w[u] + offset];

    for(int i = 0; i < tag[u].size(); i++){

        if(tag[u][i].type == 1) cnt1[tag[u][i].val] += tag[u][i].flag;

        else cnt2[tag[u][i].val] += tag[u][i].flag;

    }

    for(int v, e = adj[u]; e; e = nxt[e]){

        if((v = go[e]) == f) continue;

        dfs(v, u);

    }

    ans[u] = -cur + cnt1[w[u] + dep[u]] + cnt2[dep[u] - w[u] + offset];

}

int main(){

    freopen("h.in", "r", stdin);

    n = read(), m = read(); offset = n * 3;

    for(int i = 1; i < n; i++){int x = read(), y = read(); addEdge(x, y), addEdge(y, x);}

    pre(1, 0);

    for(int i = 1; i <= n; i++) w[i] = read();

    for(int i = 1; i <= m; i++){int u = read(), v = read(); addTag(u, v);}

    dfs(1, 0);

    for(int i = 1; i <= n; i++) wr(ans[i]), putchar(' ');

    return 0;

}

巴特西

NOIP2016 天天爱跑步 - 树上差分

题目分析：

code

最新文章

热门文章