P6626 [省选联考 2020 B 卷] 消息传递

xuyuansu · 2022-09-19 21:23:31 · 题解

简要题意

给你一个 n 个点的树，有 m 次询问，问和一个点距离为 k 的点的数量。

本题解法：点分治

首先我们需要把询问挂上树，离线处理，给每个点开个 vector 存下来。

由于是求点的个数，所以分两种情况讨论：在没有将这个询问所在的点作为当前点分治的中心时，我们要将所有询问中 k 大于当前深度的询问存下，其实就是求经过当前中心的长 k-dep[x] 的路径有多少条；当这个询问是分治中心时，直接加上答案就可以了，最后减掉不合法的情况。

实际情况中我们是不分类的，那样会增大码量，统一使用桶记录该距离有多少个点解决。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int T,n,m,ver[N*2],ne[N*2],head[N],tot,root,siz[N],son[N],ma,s,ans[N],dep[N],t[N];
bool vis[N];
void add(int x,int y)
{
    ver[++tot]=y;ne[tot]=head[x];head[x]=tot;
}
vector<pair<int,int> > v[N],q;
void getroot(int x,int fa)
{
    siz[x]=1;son[x]=0;
    for(int i=head[x];i;i=ne[i])
    {
        int y=ver[i];
        if(y==fa || vis[y]) continue;
        getroot(y,x);
        siz[x]+=siz[y];
        son[x]=max(son[x],siz[y]);
    }
    son[x]=max(son[x],s-siz[x]);
    if(son[x]<ma) ma=son[x],root=x;
}
int md;
void getdis(int x,int fa)
{
    t[dep[x]]++;md=max(md,dep[x]);
    for(auto i : v[x])
    {
        if(i.first+1<dep[x]) continue;
        q.push_back(make_pair(i.first-dep[x]+2,i.second));
    }
    for(int i=head[x];i;i=ne[i])
    {
        int y=ver[i];
        if(y==fa || vis[y]) continue;
        dep[y]=dep[x]+1;
        getdis(y,x);
    }
}
void consolate(int x)
{
    q.clear();md=0;
    dep[x]=1;getdis(x,0);
    for(auto i : q)
    {
        ans[i.second]+=t[i.first];
    }
    for(int i=1;i<=md;i++) t[i]=0;
    for(int i=head[x];i;i=ne[i])
    {
        int y=ver[i];
        if(vis[y]) continue;
        md=0;q.clear();
        dep[y]=2;getdis(y,x);
        for(auto j : q)
        {
            ans[j.second]-=t[j.first];
        }
        for(int j=1;j<=md;j++) t[j]=0;
    }
}
void divide(int rt)
{
    consolate(rt);
    vis[rt]=1;
    for(int i=head[rt];i;i=ne[i])
    {
        int y=ver[i];
        if(vis[y]) continue;
        ma=0x3f3f3f3f;s=siz[y];root=0;
        getroot(y,0);
        divide(root);
    }
}
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&m);
        memset(head,0,sizeof(head));
        memset(ans,0,sizeof(ans));
        memset(vis,0,sizeof(vis));tot=0;
        for(int i=1;i<=n;i++) v[i].clear();
        for(int i=1;i<n;i++)
        {
            int x,y;scanf("%d%d",&x,&y);
            add(x,y);add(y,x);
        }
        for(int i=1;i<=m;i++)
        {
            int x,y;scanf("%d%d",&x,&y);
            v[x].push_back(make_pair(y,i));
        }
        ma=0x3f3f3f3f,s=n;
        getroot(1,0);
        divide(root);
        for(int i=1;i<=m;i++) printf("%d\n",ans[i]);
    }
    return 0;
}