牛客 172C 保护 题解【线段树合并】【LCA】【dfs序】

点击量：177

    差点爆空间+时间= =好刺激啊……不过这个题的做法好清奇……

目录

题目描述

C国有\(n\)个城市，城市间通过一个树形结构形成一个连通图。城市编号为\(1\)到\(n\)，其中\(1\)号城市为首都。国家有\(m\)支军队，分别守卫一条路径的城市。具体来说，对于军队\(i\)，他守卫的城市区域可以由一对二元组\(x_i,y_i\)代表。表示对于所有在\(x_i\)到\(y_i\)的最短路径上的城市，军队i都会守卫他们。

 

现在有\(q\)个重要人物。对于一个重要人物\(j\)，他要从他的辖区\(v_j\)出发，去到首都。出于某些原因，他希望找到一个离首都最近的，且在\(v_j\)到首都路径上的城市\(u_j\)，使得至少有\(k_j\)支军队，能够全程保护他从\(v_j\)到\(u_j\)上所经过的所有城市。换句话说，至少有\(k_i\)支军队，满足在树上，\(x_i\)到\(y_i\)的路径能完全覆盖掉\(v_j\)到\(u_j\)的路径。

 

输入输出格式

输入格式：

第一行输入两个数\(n,m\)。

接下来\(n-1\)行，每行两个整数\(u,v\),表示存在一条从城市\(u\)到城市\(v\)的道路。

接下来\(m\)行，每行两个整数\(x,y\)。描述一个军队的守卫区域。

接下来一行一个整数\(q\)。

接下来\(q\)行，每行两个整数\(v_j,k_j\)。

 

输入格式：

对于每次询问，输出从\(v_j\)到\(u_j\)最少需要经过多少条边。假如不存在这样的\(u_j\)，则输出\(0\)。

 

输入输出样例

输入样例：

8 8
7 1
1 3
3 4
4 6
6 2
4 5
7 8
7 2
7 1
7 1
7 5
1 1
1 3
1 6
5 1
8
5 1
2 1
2 1
4 2
3 2
4 2
1 1
4 1

输出样例：

3
4
4
2
1
2
0
2

说明

\(20\%:n,m,q\le 300\)
\(40\%:n,m,q\le 2000\)
\(60\%:n,m,q\le 50000\)
\(100\%:n,m,q\le 200000\)

题解：

    首先需要理解好题意。如果对于一个重要人物\(v_i\rightarrow u_i\)满足\(d[u_i]\le d[v_i]\)，那么能保护他的一个军队\((x_i,y_i)\)，必须满足\(x_i\)在\(v_i\)的子树中，且\(y_i\)不在\(u_i\)的\(x_i\)(或\(v_i\))所在的子树中。类似这样：

    那么就有合法的\(x_i\in {u,3,4},y_i\in {v,1,2}\)。如果多存在一个军队满足这个条件，那么这条路线就多被保护一次，我们就需要顺着向上找一个位置，使得这些军队中在这个点剩下的军队恰好小于被询问的\(k\)。

    一种做法是使用bitset，每次暴力更新\(x_i\)到\(y_i\)路径上被哪队军队保护。然后把\(u_i\)和\(v_i\)存的信息做\(\mathrm{and}\)操作，得到的结果有多少个\(1\)就说明有多少个军队保护了这整条路。时间复杂度是暴力更新和查询的复杂度\(O(n^2+qn/32)\)。

    实际上我们可以维护上面的信息，对于\(u_i\)到\(v_i\)这条路见，它实际作用的范围分别是\(u_i\rightarrow lca(u_i,v_i),v_i\rightarrow lca(u_i,v_i)\)。我们只要对每一个点维护从它的子树中的点出发，到深度为\(i\)的祖先为止分别有多少个军队。

    比如说这样一条链：通过f数组可以知道，从一个点的子树中到达某个深度有多少种方案。由此可以知道从子树中出来的军队在哪里减少到\(k\)以下，等价于查询区间第\(k\)小的值。实际上这个问题可以用线段树来维护，这样查询区间第\(k\)小的值非常方便。比如说在3号节点有一个重要人物需要2个军队保护，那么它最浅能走到2号节点（深度为2），因为它的f数组中从小到大数第2种方案就是2。

    但是我们维护的是整棵子树，因此还要更新各个儿子的信息，此时就需要用到线段树合并。而同时我们开了\(n\)棵线段树，为了保证空间，需要动态开点。把原来的权值线段树与每个儿子的线段树合并；如果在一个位置，两棵线段树都没有节点，这个位置在新树上仍然不存在。如果其中一棵有节点，那么这个节点就直接赋值为存在的那个节点即可；剩下的直接递归合并，合并的时间复杂度为节点个数。

    因此我们把询问离线，dfs整棵树，从下往上处理，每次把儿子的线段树合并到自己的线段树上。合并完成后，对于每个询问，查询自己线段树上的第\(k\)小值即可。

    于是时间1800ms,空间210mb:(。。。还好良心出题人都开够了

Code：

#include<cstdio>
#include<cstring>
#include<vector>
#define mid (l+r>>1)
using std::vector;
struct node
{
    int v,l,r;
    node *ls,*rs;
    node(int l,int r)
    {
        v=0;
        this->l=l;
        this->r=r;
        ls=NULL;
        rs=NULL;
    }
    node()
    {
        ls=NULL;
        rs=NULL;
    }
    void add(int p)
    {
        ++v;
        if(l==r)
            return;
        if(p<=mid)
        {
            if(!ls)
                ls=new node(l,mid);
            return ls->add(p);
        }
        if(!rs)
            rs=new node(mid+1,r);
        return rs->add(p);
    }
    int Find(int x)//查询子树中第k大的
    {
        if(l==r)
            return l;
        int L=ls?ls->v:0;
        if(x<=L)
            return ls->Find(x);
        return rs->Find(x-L);
    }
    int ask(int L,int R)
    {
        if(!this)
            return 0;
        if(L==l&&R==r)
            return v;
        if(R<=mid)
            return ls->ask(L,R);
        return ls->ask(L,mid)+rs->ask(mid+1,R);
    }
}*root[200010];
void Merge(node *&a,node *&b)
{
    if(!a||!b)
    {
        a=a?a:b;
        return;
    }
    a->v+=b->v;
    Merge(a->ls,b->ls);
    Merge(a->rs,b->rs);
    return;
}
struct edge
{
    int n,nxt;
    edge(int n,int nxt)
    {
        this->n=n;
        this->nxt=nxt;
    }
    edge(){}
}e[400000];
int head[200010],ecnt=-1;
void add(int from,int to)
{
    e[++ecnt]=edge(to,head[from]);
    head[from]=ecnt;
    e[++ecnt]=edge(from,head[to]);
    head[to]=ecnt;
}
int f[20][200010],d[200010],n,maxd=0;
void dfs(int x)
{
    maxd=maxd>d[x]?maxd:d[x];
    for(int i=head[x];~i;i=e[i].nxt)
        if(e[i].n!=f[0][x])
        {
            d[e[i].n]=d[x]+1;
            f[0][e[i].n]=x;
            dfs(e[i].n);
        }
}
void init()
{
    for(int i=1;i<=18;++i)
        for(int j=1;j<=n;++j)
            f[i][j]=f[i-1][f[i-1][j]];
}
int lca(int x,int y)
{
    if(d[x]<d[y])
    {
        int t=x;
        x=y;
        y=t;
    }
    for(int i=18;i>=0;--i)
        if(d[f[i][x]]>=d[y])
            x=f[i][x];
    if(x==y)
        return x;
    for(int i=18;i>=0;--i)
        if(f[i][x]!=f[i][y])
        {
            x=f[i][x];
            y=f[i][y];
        }
    return f[0][x];
}
struct Ask
{
    int k,num;
    Ask(int k,int num)
    {
        this->k=k;
        this->num=num;
    }
    Ask(){}
};
vector<Ask> ask[200010];
int ans[200010];
void Dfs(int x)
{
    for(int i=head[x];~i;i=e[i].nxt)
        if(e[i].n!=f[0][x])
        {
            Dfs(e[i].n);
            Merge(root[x],root[e[i].n]);
        }
    int tmp=root[x]->ask(1,d[x]);
    for(vector<Ask>::iterator it=ask[x].begin();it!=ask[x].end();++it)
    {
        if(it->k>tmp)
            ans[it->num]=0;
        else
            ans[it->num]=d[x]-root[x]->Find(it->k);
    }

}
int main()
{
    memset(head,-1,sizeof(head));
    int m,u,v;
    scanf("%d%d",&n,&m);
    for(int i=1;i<n;++i)
    {
        scanf("%d%d",&u,&v);
        add(u,v);
    }
    f[0][1]=1;
    d[1]=1;
    dfs(1);
    init();
    for(int i=1;i<=m;++i)
    {
        scanf("%d%d",&u,&v);
        int t=lca(u,v);
        if(!root[u])
            root[u]=new node(1,maxd);
        root[u]->add(d[t]);
        if(!root[v])
            root[v]=new node(1,maxd);
        root[v]->add(d[t]);
    }
    int q;
    scanf("%d",&q);
    for(int i=1;i<=q;++i)
    {
        scanf("%d%d",&u,&v);
        ask[u].push_back(Ask(v,i));
    }
    Dfs(1);
    for(int i=1;i<=q;++i)
        printf("%d\n",ans[i]);
    return 0;
}