UOJ261 【NOIP2016】天天爱跑步 LCA+动态开点线段树

UOJ261 【NOIP2016】天天爱跑步

Description

小c同学认为跑步非常有趣,于是决定制作一款叫做《天天爱跑步》的游戏。天天爱跑步是一个养成类游戏,需要玩家每天按时上线,完成打卡任务。这个游戏的地图可以看作一一棵包含 N个结点和N-1 条边的树, 每条边连接两个结点,且任意两个结点存在一条路径互相可达。树上结点编号为从1到N的连续正整数。现在有个玩家,第个玩家的起点为Si ,终点为Ti。每天打卡任务开始时,所有玩家在第0秒同时从自己的起点出发, 以每秒跑一条边的速度,不间断地沿着最短路径向着自己的终点跑去, 跑到终点后该玩家就算完成了打卡任务。(由于地图是一棵树, 所以每个人的路径是唯一的)小C想知道游戏的活跃度, 所以在每个结点上都放置了一个观察员。在结点的观察员会选择在第Wj秒观察玩家, 一个玩家能被这个观察员观察到当且仅当该玩家在第Wj秒也理到达了结点J。小C想知道每个观察员会观察到多少人?注意: 我们认为一个玩家到达自己的终点后该玩家就会结束游戏, 他不能等待一段时间后再被观察员观察到。即对于把结点J作为终点的玩家: 若他在第Wj秒重到达终点,则在结点J的观察员不能观察到该玩家;若他正好在第Wj秒到达终点,则在结点的观察员可以观察到这个玩家。

Input

第一行有两个整数N和M 。其中N代表树的结点数量, 同时也是观察员的数量, M代表玩家的数量。

接下来n-1 行每行两个整数U和V ,表示结点U 到结点V 有一条边。

接下来一行N 个整数,其中第个整数为Wj , 表示结点出现观察员的时间。

接下来 M行,每行两个整数Si和Ti,表示一个玩家的起点和终点。

对于所有的数据,保证。

1<=Si,Ti<=N,0<=Wj<=N

Output

输出1行N 个整数,第个整数表示结点的观察员可以观察到多少人。

Sample Input

6 3
2 3
1 2
1 4
4 5
4 6
0 2 5 1 2 3
1 5
1 3
2 6

Sample Output

1 2 1 0 1

HINT

对于1号点,Wi=0，故只有起点为1号点的玩家才会被观察到，所以玩家1和玩家2被观察到，共有2人被观察到。

对于2号点，没有玩家在第2秒时在此结点，共0人被观察到。

对于3号点，没有玩家在第5秒时在此结点，共0人被观察到。

对于4号点，玩家1被观察到，共1人被观察到。

对于5号点，玩家1被观察到，共1人被观察到。

对于6号点，玩家3被观察到，共1人被观察到。

SOLUTION：

中间的测试点具体如何解决就不再赘述，详见大佬博客：https://www.cnblogs.com/ljh2000-jump/p/6189053.html

先面说正解：

这道题是一个树形结构，从S_i到T_i的路径唯一，且一定经过两点的lca

我们可以把路径拆成两段，S到lca，lca到T

我们考虑第一种情况，若有一个观察员在S到lca的路径x上，若想观察员有贡献，当且仅当deep[S]-deep[x]=W[x];

移项可得：deep[S]=deep[x]+W[x]，转化为在S到lca的路径上添加deep[S]这种物品，求每个点deep[x]+W[x]这一种物品数量;

我们先处理出每个S和T的lca以及每个点的管辖区间（dfs序），[dfs_in[i],dfs_out[i]]为节点i个区间

我们可以对每个deep[S_i]建立一个动态开点线段树，在dfs_in[Si]处加一，运用差分思想，在dfs_in[father[lca]]处该物品减一。

加完点后我们对每一个节点进行查询，i点能看到的玩家数量就是在以deep[x]+W[x]的线段树中对区间[dfs_in[i],dfs_out[i]]求和所的的结果;

对于第二种情况，我们能写出deep[Si]+deep[x]-2*deep[lca]=W[x],移项得deep[Si]-2*deep[lca]=W[x]-deep[x];

同样对每个deep[Si]-2*deep[lca]建线段树，求W[x]-deep[x]这一种物品数量，但这一次是在dfs_in[lca]处减一;（用差分一想就明白了）

最后类加两次求得的答案即可。

ps：deep[Si]-2*deep[lca]可能为负数，可以以deep[Si]-2*deep[lca]+2×n建线段树，注意数组开三倍

lca博主用的树链剖分，顺便求dfs序。

之前博主并不会树链剖分，所以这一次学习了之后拿来练习一下

线段树进阶部分博主也是在打道题时学习的。

放码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#define MAXN 300001
#define MAXM 10000001
using namespace std;
int n, m, w[MAXN], s[MAXN], t[MAXN], lca[MAXN], ans[MAXN];
int tot_e, to[2 * MAXN], nxt[2 * MAXN], pre[MAXN];
void add(int u, int v) { tot_e++, to[tot_e] = v, nxt[tot_e] = pre[u], pre[u] = tot_e; }
int deep[MAXN], fa[MAXN], son[MAXN], size[MAXN];
void dfs(int u, int f, int dep) {
    fa[u] = f;
    deep[u] = dep;
    size[u] = 1;
    for (int i = pre[u]; i; i = nxt[i]) {
        int v = to[i];
        if (v == f)
            continue;
        dfs(v, u, dep + 1);
        size[u] += size[v];
        if (size[v] > size[son[u]])
            son[u] = v;
    }
}
int top[MAXN], dfs_in[MAXN], dfs_out[MAXN], rk[MAXN], dfs_order = 0;
void DFS(int u, int top_chain) {
    top[u] = top_chain;
    dfs_in[u] = ++dfs_order;
    rk[dfs_order] = u;
    if (!son[u]) {
        dfs_out[u] = dfs_order;
        return;
    }
    DFS(son[u], top_chain);
    for (int i = pre[u]; i; i = nxt[i]) {
        int v = to[i];
        if (v != son[u] && v != fa[u])
            DFS(v, v);
    }
    dfs_out[u] = dfs_order;
}
int LCA(int x, int y) {
    while (top[x] != top[y]) {
        if (deep[top[x]] < deep[top[y]])
            swap(x, y);
        x = fa[top[x]];
    }
    return deep[x] < deep[y] ? x : y;
}
int tot_root = 0, ls[MAXM], rs[MAXM], sum[MAXM], root[MAXM];
void update(int &now, int l, int r, int pos, int val) {
    if (!pos)
        return;
    if (!now)
        now = ++tot_root;
    sum[now] += val;
    if (l == r)
        return;
    int mid = (l + r) >> 1;
    if (pos <= mid)
        update(ls[now], l, mid, pos, val);
    else
        update(rs[now], mid + 1, r, pos, val);
}
int query(int rt, int L, int R, int l, int r) {  //[l,r]:目标区间，[L,R]:总区间
    if (!rt)
        return 0;
    if (L == l && r == R)
        return sum[rt];
    int mid = (L + R) >> 1;
    if (r <= mid)
        return query(ls[rt], L, mid, l, r);
    else if (l > mid)
        return query(rs[rt], mid + 1, R, l, r);
    else
        return query(ls[rt], L, mid, l, mid) + query(rs[rt], mid + 1, R, mid + 1, r);
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1, u, v; i < n; i++) {
        scanf("%d%d", &u, &v);
        add(u, v), add(v, u);
    }
    for (int i = 1; i <= n; i++) scanf("%d", &w[i]);
    dfs(1, 0, 1);
    DFS(1, 0);
    for (int i = 1; i <= m; i++) {
        scanf("%d%d", &s[i], &t[i]);
        lca[i] = LCA(s[i], t[i]);
    }
    for (int i = 1; i <= m; i++) {
        update(root[deep[s[i]]], 1, n, dfs_in[s[i]], 1);
        update(root[deep[s[i]]], 1, n, dfs_in[fa[lca[i]]], -1);
    }
    for (int i = 1; i <= n; i++) 
        ans[i] = query(root[deep[i] + w[i]], 1, n, dfs_in[i], dfs_out[i]);
    tot_root = 0;
    memset(ls, 0, sizeof(ls));
    memset(rs, 0, sizeof(rs));
    memset(sum, 0, sizeof(sum));
    memset(root, 0, sizeof(root));
    for (int i = 1; i <= m; i++) {
        update(root[deep[s[i]] - 2 * deep[lca[i]] + 2 * n], 1, n, dfs_in[t[i]], 1);
        update(root[deep[s[i]] - 2 * deep[lca[i]] + 2 * n], 1, n, dfs_in[lca[i]], -1);
    }
    for (int i = 1; i <= n; i++) ans[i] += query(root[w[i] - deep[i] + 2 * n], 1, n, dfs_in[i], dfs_out[i]);
    for (int i = 1; i <= n; i++) printf("%d ", ans[i]);
    puts("");
    return 0;
}