Noip 2016 天天爱跑步解题报告

                                            wsndy
                                            18.05.04

题解

题面

小c同学认为跑步非常有趣,于是决定制作一款叫做《天天爱跑步》的游戏。《天天爱跑步》是一个养成类游戏,需要玩家每天按时上线,完成打卡任务。

这个游戏的地图可以看作一一棵包含 $n$ 个结点和 $n-1$ 条边的树, 每条边连接两个结点,且任意两个结点存在一条路径互相可达。树上结点编号为从 $1$ 到 $n$ 的连续正整数。

现在有 $m$ 个玩家,第 $i$ 个玩家的起点为 $S_i$ ,终点为 $T_i$。每天打卡任务开始时,所有玩家在第 $0$ 秒同时从自己的起点出发, 以每秒跑一条边的速度, 不间断地沿着最短路径向着自己的终点跑去, 跑到终点后该玩家就算完成了打卡任务。 (由于地图是一棵树, 所以每个人的路径是唯一的)

小C想知道游戏的活跃度, 所以在每个结点上都放置了一个观察员。 在结点 $j$ 的观察员会选择在第 $W_j$ 秒观察玩家, 一个玩家能被这个观察员观察到当且仅当该玩家在第 $W_j$ 秒也理到达了结点 $j$ 。小C想知道每个观察员会观察到多少人?

注意: 我们认为一个玩家到达自己的终点后该玩家就会结束游戏, 他不能等待一段时间后再被观察员观察到。 即对于把结点 $j$ 作为终点的玩家: 若他在第 $W_j$ 秒前到达终点,则在结点 $j$ 的观察员不能观察到该玩家;若他正好在第 $W_j$ 秒到达终点,则在结点 $j$ 的观察员可以观察到这个玩家。

---

题意

存在一棵树，树上的每个节点有一个观察时间，如果一条路径从起点到终点的过程中经过这个点的时间(从起点出发的时间为 $0$， 每经过一条边花费时间为 $1$)与这个点的观察时间相同，那么这个点就会观察到这条路径，询问 $m$ 条路径后每个节点观察到的路径数量。

---

前置知识

    lca - 对路径划分
    树链剖分 - 求lca，化树成链
    树上差分 - 统计
    线段树 (动态开节点) - 统计

---

变量表达

    deep[a]  节点a的深度
    wat[a]   节点a出现观察员的时间 //watch
    s        一条路径的起点，代码中用Askl[]表示
    t        一条路径的终点，代码中用Askr[]表示
    lca(a,b) a,b 的lca

---

思考

对于树上的问题往往将树上的一段路径拆成 $s - lca$ 和 $lca - t$ 两条路径来处理

解

首先将路径拆成 $s - lca$ 和 $lca - t$ 两段路径
对于 $s - lca$ 是向上的路径,如果该路径能被 $i$ 节点观察到，我们就可以得到

$$deep[s] - deep[i] = wat[i]$$ $$deep[s] = wat[i] + deep[i]$$
显然对与节点 $i$ ，它能观察到的向上跑的玩家，是所有的 $$s=deep[i]+watch[i]$$ 的玩家
也就是说在以 $i$ 为根的子树中(涉及链剖的思想)所有路径起点深度为 $deep[i] + wat[i]$ 的路径都可以被节点 $i$ 观察到
这里考虑树剖的第 $2$ 个 $Dfs$ 就可以处理以 $i$ 为根的子树，将以 $i$ 为根的子树转化为一段区间 $[lst, rst]$
然后，对每一个深度都建立一颗线段树(空间不够，动态开点)，那么就可以在深度为 $deep[i] + wat[i]$ 的线段树中查询区间 $[lst, rst]$ 被观察到的路径条数
注意线段树维护的是该深度下路径起点的个数，那么查询该深度中的某段区间，就相当于查询该深度下该区间中的路径的起点个数
如何标记观察到的路径条数??
考虑差分
在 $s$ 处 $-1$ ,在 $lca$ 的父亲节点处 $+1$
这里可以对照序列差分理解
这样就可以进行区间和的统计啦

同理，对于 $lca - t$ 的这段路径

$$deep[s]+deep[i]-2*deep[lca(s,i)]=wat[i]$$ $$deep[s]-2*deep[lca(s,i)]=watch[i]-deep[i]$$
这样在 $watch[i]-deep[i]$ 深度为 $deep[s]-2*deep[lca(s,i)]$ 的线段树中，终点处 $+1$ ，$lca$ 处 $-1$，注意这里是在 $lca$ 处 $-1$， 防止 $lca$ 处多加
查询时查询深度为 $wat[i]-deep[i]$ 的线段树即可
由于 $wat[i]-deep[i]$ 可能出现负数，所以要加一个数，使深度不为负数。

---

Code

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 3e5 + 10;
#define gc getchar()
int n, m, wat[N];
int Askl[N], Askr[N], Lca[N];
int now = 1, head[N];
struct Node {int v, nxt;} G[N << 1];
inline int read() {
    int x = 0; char c = gc;
    while(c < '0' || c > '9') c = gc;
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = gc;
    return x;
}
inline void Add(int u, int v) {G[now].v = v; G[now].nxt = head[u]; head[u] = now ++;}
int fa[N], deep[N], top[N], size[N], son[N], lst[N], rst[N], tree[N], Spjs;
void Dfs_1(int u, int f_, int dep) {
    fa[u] = f_; deep[u] = dep; size[u] = 1;
    for(int i = head[u]; ~ i; i = G[i].nxt) {
        int v = G[i].v;
        if(v != f_) {
            Dfs_1(v, u, dep + 1);
            size[u] += size[v];
            if(size[son[u]] < size[v]) son[u] = v;
        }
    }
}
void Dfs_2(int u, int tp) {
    top[u] = tp;
    lst[u] = ++ Spjs;
    tree[u] = Spjs;
    if(! son[u]) {rst[u] = Spjs; return ;}
    Dfs_2(son[u], tp);
    for(int i = head[u]; ~ i; i = G[i].nxt) {
        int v = G[i].v;
        if(v != fa[u] && v != son[u]) Dfs_2(v, v);
    }
    rst[u] = Spjs;
}
inline int Ask_Lca(int x, int y) {
    int tp1 = top[x], tp2 = top[y];
    while(tp1 != tp2) {
        if(deep[tp1] < deep[tp2]) swap(x, y), swap(tp1, tp2);
        x = fa[tp1];
        tp1 = top[x];
    }
    return deep[x] < deep[y] ? x : y;
}
int root[N * 3], lson[N * 25], rson[N * 25], W[N * 25], tot, cnt;
void Build_G(int l, int r, int & jd, int x, int yj) {
    if(!x) return ;
    if(!jd) jd = ++ tot;
    W[jd] += yj;
    if(l == r) return ;
    int mid = (l + r) >> 1;
    if(x <= mid) Build_G(l, mid, lson[jd], x, yj);
    else Build_G(mid + 1, r, rson[jd], x, yj);
}
int Sec_A(int jd, int l, int r, int x, int y) {
    if(! jd) return 0;
    if(x <= l && r <= y) return W[jd];
    int mid = (l + r) >> 1;
    if(y <= mid) return Sec_A(lson[jd], l, mid, x, y);
    else if(x > mid) return Sec_A(rson[jd], mid + 1, r, x, y);
    else return Sec_A(lson[jd], l, mid, x, y) + Sec_A(rson[jd], mid + 1, r, x, y);
}
void Clear() {
    tot = 0;
    memset(lson, 0, sizeof lson);
    memset(rson, 0, sizeof rson);
    memset(W, 0, sizeof W);
    memset(root, 0, sizeof root);
}
int Answer[N];
int main() {
    n = read(); m = read();
    for(int i = 1; i <= n; i ++) head[i] = -1;
    for(int i = 1; i <= n - 1; i ++) {
        int u = read(), v = read();
        Add(u, v); Add(v, u);
    }
    for(int i = 1; i <= n; i ++) wat[i] = read();
    for(int i = 1; i <= m; i ++) Askl[i] = read(), Askr[i] = read(); 
    Dfs_1(1, 0, 0);
    Dfs_2(1, 1);
    for(int i = 1; i <= m; i ++) Lca[i] = Ask_Lca(Askl[i], Askr[i]);
    int dep;
    for(int i = 1; i <= m; i ++) {
        dep = deep[Askl[i]];
        Build_G(1, n, root[dep], tree[Askl[i]], 1);
        Build_G(1, n, root[dep], tree[fa[Lca[i]]], -1);
    }
    for(int i = 1; i <= n; i ++) 
        Answer[i] = Sec_A(root[deep[i] + wat[i]], 1, n, lst[i], rst[i]);
    Clear();
    for(int i = 1; i <= m; i ++) {
        dep = deep[Askl[i]] - deep[Lca[i]] * 2 + n * 2;
        Build_G(1, n, root[dep], tree[Askr[i]], 1);
        Build_G(1, n, root[dep], tree[Lca[i]], -1);
    }
    for(int i = 1; i <= n; i ++)
        Answer[i] += Sec_A(root[wat[i] - deep[i] + n * 2], 1, n, lst[i], rst[i]);
    for(int i = 1; i <= n; i ++) 
        cout << Answer[i] << " ";
    return 0;
}