「题解」「联合省选 2020 B」信息传递 message

题目链接:联合省选 2020 B D1T2/Luogu P6626/LibreOJ 3306

题目

题目描述

给定一个包含 $n$ 个人(从 $1$ 到 $n$ 编号)的树形社交网络。如果一个人在某天收到了一条消息,则下一天他会将消息传递给所有与他有直接社交关系的人。

现在有 $m$ 次询问,每次询问假定第 $0$ 天 $x$ 号人收到了一条消息,请你计算第 $k$ 天时新收到此条消息的人数(即第 天前收到过此条消息的人不计入其中)。不同询问间互不影响。

本题有多组数据,数据组数为 $T$。

数据范围

对于测试点 $1$:$1\leq n,m\leq 10$。

对于测试点 $2$:$1\leq n,m\leq 100$。

对于测试点 $3$:$1\leq n,m\leq 1000$。

对于测试点 $4\sim 6$:$1\leq n,m\leq 10^5,k\leq 20$。

对于测试点 $7\sim 10$:$1\leq n,m\leq 10^5$。

对于所有测试点:$1\leq T\leq 5,1\leq x\leq n,0\leq k<n$。

时空限制

题目编号时间限制空间限制
联合省选 2020 B D1T2$2\text{s}$$256\text{MiB}$

题解

本题有部分分解法。在这之前我们先描述一下问题,$m$ 此询问,问你到 $x$ 距离为 $k$ 的点有多少个。

解法 A(暴力)

对于测试点 $1$:$1\leq n,m\leq 10$。
对于测试点 $2$:$1\leq n,m\leq 100$。
对于测试点 $3$:$1\leq n,m\leq 1000$。


从每个点出发遍历整棵树一边,得到到每个点距离为 $x$ 的点的个数,记录一下即可。

时间复杂度为 $\Theta(n^2)$,期望得分 $30$ 分。

解法 B(深度有限制的暴力)

对于测试点 $4\sim 6$:$1\leq n,m\leq 10^5,k\leq 20$。


发现 $k$ 不会很大,可以考虑换根 $\texttt{DP}$。

剩下的都是套路。

时间复杂度为 $\Theta(n\times\max\{k\})$,期望得分为 $60$ 分。

解法 C(没有用的解法)

长链剖分,预计得分 $30$ 分,具体我就不说了,时间复杂度为 $\Theta(n^2)$。

解法 D(正解)

对于所有测试点:$1\leq T\leq 5,1\leq n,m\leq 10^5,1\leq x\leq n,0\leq k<n$。


考虑点分治。

指定一个点(重心)为根,那么对于任意一个非根的节点 $x$,与它距离为 $k$ 的点无非会有两种情况:子树内或子树外。

对于在子树外的节点,用一个桶来记录各个节点与根的关系。即 $\texttt{T} _ i$ 表示与根距离为 $i$ 的点的个数。

如果一个子树外的点 $y$ 与 $x$ 的距离为 $k$,那么它们一定满足 $\text{dep} _ x+\text{dep} _ y=k$。所以可以直接把对应的桶 $\texttt{T} _ {k-\text{dep} _ x}$ 计入答案。

而子树内的结点,分治处理即可。时间复杂度 $\Theta(n\log _ 2n)$。

#include<bits/stdc++.h>
using namespace std;
#define reg register
#define INF 0X3F3F3F3F
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
static char buf[100000],*p1=buf,*p2=buf;
inline int read(void){
    reg char ch=getchar();
    reg int res=0;
    while(ch<'0'||'9'<ch)ch=getchar();
    while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar();
    return res;
}

const int MAXN=100000+5;
const int MAXM=100000+5;

inline void Read(void);
inline void Work(void);

int main(void){
    reg int T=read();
    while(T--){
        Read();
        Work();
    }
    return 0;
}

int n,m;
int ans[MAXM];
bool vis[MAXN];
int cnt,head[MAXN],to[MAXN<<1],Next[MAXN<<1];

inline void Add_Edge(reg int u,reg int v){
    Next[++cnt]=head[u];
    to[cnt]=v;
    head[u]=cnt;
    return;
}

vector<pair<int,int>/**/> q[MAXN];

inline void Read(void){
    n=read(),m=read();
    cnt=0;
    for(reg int i=1;i<=n;++i)
        head[i]=0,q[i].clear(),vis[i]=false;
    for(reg int i=1;i<n;++i){
        static int a,b;
        a=read(),b=read();
        Add_Edge(a,b);
        Add_Edge(b,a);
    }
    for(int i=1;i<=m;++i){
        static int x,k;
        x=read(),k=read();
        if(k==0)
            ans[i]=1;
        else{
            q[x].push_back(make_pair(i,k));
            ans[i]=0;
        }
    }
    return;
}

int tot,Min;
int root;
int size[MAXN];

inline void find(reg int ID,reg int father){
    int Max=0;
    size[ID]=1;
    for(reg int i=head[ID];i;i=Next[i]){
        reg int v=to[i];
        if(v!=father&&!vis[v]){
            find(v,ID);
            size[ID]+=size[v];
            Max=max(Max,size[v]);
        }
    }
    Max=max(Max,tot-size[ID]);
    if(Max<Min){
        root=ID;
        Min=Max;
    }
    return;
}

int T[MAXN];

inline void Query(reg int ID,reg int father,reg int dep){
    for(reg int i=0,size=q[ID].size();i<size;++i){
        if(q[ID][i].second>=dep)
            ans[q[ID][i].first]+=T[q[ID][i].second-dep];
    }
    for(reg int i=head[ID];i;i=Next[i]){
        reg int v=to[i];
        if(v!=father&&!vis[v])
            Query(v,ID,dep+1);
    }
    return;
}

int top,S[MAXN];

inline void Update(reg int ID,reg int father,reg int dep){
    ++T[dep],S[++top]=dep;
    for(reg int i=head[ID];i;i=Next[i]){
        reg int v=to[i];
        if(v!=father&&!vis[v])
            Update(v,ID,dep+1);
    }
    return;
}

inline void Solve(reg int ID){
    vis[ID]=true;
    ++T[0];
    S[++top]=0;
    int St[MAXN];
    reg int topt=0;
    for(reg int i=head[ID];i;i=Next[i]){
        reg int v=to[i];
        if(!vis[v]){
            St[++topt]=v;
            Query(v,0,1);
            Update(v,0,1);
        }
    }
    while(top)
        T[S[top--]]=0;
    while(topt){
        reg int v=St[topt--];
        Query(v,0,1);
        Update(v,0,1);
    }
    for(reg int i=0,size=q[ID].size();i<size;++i)
        ans[q[ID][i].first]+=T[q[ID][i].second];
    while(top)
        T[S[top--]]=0;
    for(reg int i=head[ID];i;i=Next[i]){
        reg int v=to[i];
        if(!vis[v]){
            tot=size[v],Min=INF;
            find(v,0);
            Solve(root);
        }
    }
    return;
}

inline void Work(void){
    tot=n,Min=INF;
    find(1,0);
    Solve(root);
    for(reg int i=1;i<=m;++i)
        printf("%d\n",ans[i]);
    return;
}