专栏首页数据结构与算法牛客NOIP提高组R1 C保护(主席树)

牛客NOIP提高组R1 C保护(主席树)

题意

题目链接

Sol

Orz lyq

我们可以把一支军队(u, v)拆分为两个(u, lca)和(v, lca)

考虑一个点x,什么时候军队对它有贡献,肯定是u或v在他的子树内,且lca在他的子树外

因为需要让至少k个军队能够完全覆盖,所以肯定是选深度第k小的

这个过程可以用dfs序+主席树来实现

拿(u, lca)来说,在dfn[u]对应的线段树中,dep[lca]处+1即可。

然后查第k大即可

/**/
#include<cstdio>
#include<vector>
using namespace std;
const int MAXN = 2 * 1e5 + 10;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int N, M;
struct Node {
    int siz;
}T[MAXN * 70];
int root[MAXN * 70], ls[MAXN * 70], rs[MAXN * 70];
int dep[MAXN], fa[MAXN], top[MAXN], siz[MAXN], son[MAXN], deep[MAXN], dfn[MAXN], cnt, tot, num, ID[MAXN];
vector<int> v[MAXN], Q[MAXN];//Q[i] dfs搴忎负i鐨勯渶瑕佸姞鍏ョ殑鍏冪礌
void dfs1(int x, int _fa) {
    dfn[x] = ++cnt;
    fa[x] = _fa; siz[x]= 1; deep[x] = deep[_fa] + 1;
    for(int i = 0; i < (int)v[x].size(); i++) {
        int to = v[x][i];
        if(to == _fa) continue;
        dfs1(to, x);
        siz[x] += siz[to];
        if(siz[to] > siz[son[x]]) son[x] = to;
    }
}
void dfs2(int x, int topf) {
    top[x] = topf;
    if(!son[x]) return ;
    dfs2(son[x], topf);
    for(int i = 0; i < (int)v[x].size(); i++) {
        int to = v[x][i];
        if(top[to]) continue;
        dfs2(to, to);
    }
}
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]];
    }
    if(deep[x] > deep[y]) swap(x, y);
    return x;
}
void Insert(int &k, int p, int l, int r, int pos) {
    if(l > r) return ;
    if(!k) k = ++tot, T[k].siz = T[p].siz + 1;
    if(l == r) return ;
    int mid = (l + r) >> 1;
    if(pos <= mid) rs[k] = rs[p], Insert(ls[k], ls[p], l, mid, pos);
    else ls[k] = ls[p], Insert(rs[k], rs[p], mid + 1, r, pos);
}
int Query(int rl, int rr, int k, int l, int r) {
    if(T[rr].siz - T[rl].siz < k) return 0;
    if(l == r) return k > (T[rr].siz - T[rl].siz) ? 0 : l;
    int si = T[ls[rr]].siz - T[ls[rl]].siz;
    int mid = (l + r) >> 1;
    if(si >= k) return Query(ls[rl], ls[rr], k, l, mid);
    else return Query(rs[rl], rs[rr], k - si, mid + 1, r);
}
int main() {
  //  freopen("a.in", "r", stdin);
  //  freopen("b.out", "w", stdout);
    N = read(); M = read();
    for(int i = 1; i <= N - 1; i++) {
        int x = read(), y = read();
        v[x].push_back(y);
        v[y].push_back(x);
    }
    dfs1(1, 0);
    dfs2(1, 1);
    for(int i = 1; i <= M; i++) {
        int x = read(), y = read(), lca = LCA(x, y);
        Q[dfn[x]].push_back(deep[lca]);
        Q[dfn[y]].push_back(deep[lca]);
    }
    for(int i = 1; i <= N; i++) {
        for(int j = 0; j < (int)Q[i].size(); j++) {
            int x = Q[i][j];
            ++num;
            Insert(root[num], root[num - 1], 1, N, x);
        }
        ID[i] = num;
    }
    int Q = read();
    while(Q--) {
        int u = read(), k = read();
        int ans = Query(root[ID[dfn[u] - 1]], root[ID[dfn[u] + siz[u] - 1]], k, 1, N);
        if(ans == 0 || (deep[u] - ans <= 0)) printf("0\n");
        else printf("%d\n", deep[u] - ans);
    }
    return 0;
}
/**/

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • cf1043D. Mysterious Crime(二分 前缀和)

    因此我们按照\(x - y\)排序,对于每个位置,肯定是某一个前缀全选\(x+b\),除此之外都是\(y+a\)

    attack
  • HDU1878 欧拉回路

    Problem Description 欧拉回路是指不令笔离开纸面,可画过图中每条边仅一次,且可以回到起点的一条回路。现给定一个图,问是否存在欧拉回路? Inp...

    attack
  • 洛谷P2312 解方程(暴力)

    对于\(a[i]\)取模之后再判断就行了。注意判断可能会出现误差,可以多找几个模数

    attack
  • 传参传的到底是什么?

    本人在封装一些基本方法的时候遇到过一个问题,我把对象当做参数传到方法里,然后在方法中对这个对象进行了一些修改,但是等我再去输出对象的值和属性时,却发现这些数据并...

    FunTester
  • HDU1878 欧拉回路

    Problem Description 欧拉回路是指不令笔离开纸面,可画过图中每条边仅一次,且可以回到起点的一条回路。现给定一个图,问是否存在欧拉回路? Inp...

    attack
  • cf1043D. Mysterious Crime(二分 前缀和)

    因此我们按照\(x - y\)排序,对于每个位置,肯定是某一个前缀全选\(x+b\),除此之外都是\(y+a\)

    attack
  • [三]基础数据类型之Integer详解

    noteless
  • SPOJ 375 边操作

    给一颗树,每条边有一个权值。有两种操作:1、修改某条边的值;2、询问a、b两点路径上边权的最大值。

    用户2965768
  • 经典笔试题-JAVA实现快速排序算法

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    cwl_java
  • 图论--网络流--费用流POJ 2195 Going Home

    On a grid map there are n little men and n houses. In each unit time, every litt...

    风骨散人Chiam

扫码关注云+社区

领取腾讯云代金券