Chlience

【题解】[NOIP2016]天天爱跑步 NOIP瞎搞系列
这道题被誉为 NOIP 2016 最难确实还是有点难度,当然现在看来还是比较好做的传送门 >ω< BZOJ传送门 ...
扫描右侧二维码阅读全文
16
2018/10

【题解】[NOIP2016]天天爱跑步 NOIP瞎搞系列

这道题被誉为 NOIP 2016 最难
确实还是有点难度,当然现在看来还是比较好做的

传送门 >ω< BZOJ
传送门 >ω< UOJ
传送门 >ω< Luogu

Solution

考虑每个人路径与最后答案的关系

对于 $S - T$ 这样一条路径来说
如果 路径上 某个点 $x$ 满足 $w[x] = lenth(S - x)$,则 $x$ 上的观察员能看到这个人

分开解决两个限制

限制一

什么时候 $x$ 出现在路径 $S - T$ 上

思路

考虑拆成两条路径 $S - LCA$ $LCA-T$ 分别判断

考虑 $S - LCA$ 的情况, $LCA - T$ 同理

假设 $S$ 在以 $x$ 为根的树中, $x$ 在以 $LCA$ 为根的树中

而 $S - LCA$ 是一条深度逐渐减小,最终到达祖先节点的路径 ,而 $S - x - LCA$ 同样也是一条深度逐渐减小,最终到达祖先节点的路径
在树上若从同一个点出发到某个祖先节点,有且仅有一条路径,所以 $S - LCA \Leftrightarrow S - x - LCA$

即 $x$ 在路径 $S - LCA$ 上

实现

给 $S ,T$ 的 $begin$ 标记 $+1$
给 $LCA$ 的 $end$ 标记 $+2$ (由深到浅的两条路径都是在 $LCA$ 处结束)

设当前点为 $x$
向下深搜 遇到 $begin$ 标记,加上,说明 $S$ 在 $x$ 为根的树中,遇到 $end$ 标记,减去,说明 $LCA$ 在 $x$ 为根的树中,即 $x$ 不在以 $LCA$ 为根的树中

是这样么?

并不是,因为 $LCA$ 在 $x$ 为根的树中,不意味着 $x$ 不在以 $LCA$ 为根的树中,当 $x = LCA$ 时,在统计当前点答案时就不需要减这个点,而应在统计完答案之后减去

所以我们将两个操作分开:
向下深搜时处理 $begin$
搜完后处理答案
回溯时处理 $end$

这样就保证了答案的正确性

限制二

什么时候 $w[x] = lenth(S - x)$

思路

延续之前的想法,分段考虑
若 $x$ 在 $S - LCA$ 上,则变为 $w[x] = dep[S] - dep[x]$ ,即 $dep[x] + w[x] = dep[S]$
若 $x$ 在 $LCA - T$ 上,则变为 $w[x] = (dep[x] - dep[LCA]) + (dep[S] - dep[LCA])$ ,即 $w[x] - dep[x] = dep[S] - 2*dep[LCA]$

实现

设当前点为 $x$
深搜时 记录子树中点的深度
统计答案
回溯时,在桶中删除当前点贡献

合并

最后一个问题就是如何将两个限制合并
若是 $S - LCA$ 这个部分
本来是在 $S$ 处 $begin$ $+1$ , $T$ 处 $end$ $+1$

观察到当这个标记有贡献时,当且仅当 $dep[x] + w[x] = dep[S]$ ,也就是说仅仅和 $dep[S]$ 相关
所以我们将 $begin$ 开成一个桶,在 $S$ 处 $begin[dep[s]]$ $+1$ , 在 $T$ 处 $end[dep[s]]$ $+1$ ,统计答案时记录 $\sum begin[dep[x] + w[x]] - \sum end[dep[x] + w[x]]$ 即可同时满足两个限制

若是 $LCA - T$ 这个部分
本来是在 $T$ 处 $begin$ $+1$ , $LCA$ 处 $end$ $+1$

观察到当这个标记有贡献时,当且仅当 $w[x] - dep[x] = dep[S] - 2*dep[LCA]$ , 也就是说仅仅和 $dep[S] , dep[LCA]$ 相关
同样我们开一个桶,在 $T$ 处 $begin[dep[S] - 2 * dep[LCA]]$ $+1$ , 在 $LCA$ 处 $end[dep[S] - 2 * dep[LCA]$ $-1$ , 统计答案时记录 $\sum begin[w[x] - dep[x]] - \sum end[w[x] - dep[x]]$ 即可

这两个桶是不能和为一个的啊!!!
这是不同的桶啊!!!

同样,为了实现子树求和
在进入某个点时,先记录下当前标记的状态
在搜完这个点的子树,统计答案时,减去初始状态,即为子树和

最后

注意如果一个点满足条件并且它是 $S - T$ 的 $LCA$ ,则会被统计两次,在算 $LCA$ 时减去即可

代码

#include <bits/stdc++.h>
using namespace std;
int read() {
    int ans = 0 , flag = 1;
    char ch = getchar();
    while(ch > '9' || ch < '0') {if(ch == '-') flag = - flag; ch = getchar();}
    while(ch >= '0' && ch <= '9') {ans = ans * 10 + ch - '0'; ch = getchar();}
    return ans * flag;
}
const int N = 300000;

struct edge {int t , n;}e[N << 1];
int head[N] , tot;
void addedge(int u , int v) {
    ++ tot;
    e[tot].t = v;
    e[tot].n = head[u];
    head[u] = tot;
}

int dep[N];
int w[N];
int n , m;

struct BZ {
    int fa[N][20];
    void prepare() {
        for(int j = 1 ; j < 20 ; ++ j)
            for(int i = 1 ; i <= n ; ++ i)
                fa[i][j] = fa[fa[i][j - 1]][j - 1];
    }
    int lca(int a , int b) {
        if(dep[a] < dep[b]) swap(a , b);
        for(int i = 19 ; i >= 0 ; -- i)
            if(dep[fa[a][i]] >= dep[b])
                a = fa[a][i];
        if(a == b) return a;
        for(int i = 19 ; i >= 0 ; -- i)
            if(fa[a][i] != fa[b][i]) {
                a = fa[a][i];
                b = fa[b][i];
            }
        return fa[a][0];
    }
}Jump;
//倍增 lca
void dfs(int x , int f) {
    Jump.fa[x][0] = f;
    dep[x] = dep[f] + 1;
    for(int i = head[x] ; i ; i = e[i].n) {
        if(e[i].t == f) continue;
        dfs(e[i].t , x);
    }
}

vector <int> up[N] , down[N];
vector <int> del_up[N] , del_down[N];

int ins_up[N << 1] , ins_down[N << 1];
int ans[N];

void DFS(int x , int f) {
    ans[x] -= ins_up[w[x] + dep[x]];
    ans[x] -= ins_down[w[x] - dep[x] + n];
    //这是初始状态,分为上 and 下,分别对应 s - lca 和 lca - t
    //先减去初始状态
    auto begin = up[x].begin() , end = up[x].end();
    for(auto i = begin ; i != end ; ++ i) ++ ins_up[*i];
    //加上所有 s 的标记
    begin = down[x].begin(); end = down[x].end();
    for(auto i = begin ; i != end ; ++ i) ++ ins_down[*i];
    //加上所有 t 的标记
    for(int i = head[x] ; i ; i = e[i].n) {
        if(e[i].t == f) continue;
        DFS(e[i].t , x);
    }
    //深搜
    ans[x] += ins_up[w[x] + dep[x]];
    ans[x] += ins_down[w[x] - dep[x] + n];
    //算答案,因为前面已经减去了初始状态所以直接加
    begin = del_up[x].begin() , end = del_up[x].end();
    for(auto i = begin ; i != end ; ++ i) -- ins_up[*i];
    //减去所有 s - lca 中 lca 的标记
    begin = del_down[x].begin(); end = del_down[x].end();
    for(auto i = begin ; i != end ; ++ i) -- ins_down[*i];
    //减去所有 lca - t 中 lca 的标记
}

int main() {
    n = read(); m = read();
    for(int i = 1 ; i < n ; ++ i) {
        int x = read() , y = read();
        addedge(x , y);
        addedge(y , x);
    }
    dfs(1 , 0);
    Jump.prepare();
    for(int i = 1 ; i <= n ; ++ i) w[i] = read();
    for(int i = 1 ; i <= m ; ++ i) {
        int x = read() , y = read();
        int lca = Jump.lca(x , y);
        
        up[x].push_back(dep[x]);
        del_up[lca].push_back(dep[x]);
        //s - lca
        down[y].push_back(dep[x] - 2 * dep[lca] + n);
        del_down[lca].push_back(dep[x] - 2 * dep[lca] + n);
        //lca - t
        if(dep[x] - dep[lca] == w[lca]) -- ans[lca];
        //刚好是 lca 然后又有贡献,减去一个
    }
    DFS(1 , 0);
    for(int i = 1 ; i <= n ; ++ i) printf("%d " , ans[i]);
    return 0;
}
Last modification:October 16th, 2018 at 09:03 pm
If you think my article is useful to you, please feel free to appreciate

Leave a Comment