题解 CF161D 【Distance in Tree】

Graphcity · 2020-04-06 20:19:17 · 题解

这道题可以使用点分治的方法来做。

不会点分治的可以来看看这个博客：there

我们可以这样做：将标记距离的数组（这里定义的是 alive 数组）改为 int 类型，把它重新定义为之前子树到根距离的个数，新增一个 Right 变量表示正确答案个数，我们就可以这样子做了：

        for(register int j=1;j<=nowdis;++j)
            if(q>=now[j])
                Right+=alive[q-now[j]];

统一处理距离的时候，只要把模板题里面的 true, false 改为 ++ 和 - - 操作即可。

完整代码如下：

#include<bits/stdc++.h>
#define Maxn int(5e4)
#define Maxk int(5e4)
using namespace std;

//===============邻接表=================

struct Node
{
    int to,nxt,w;
} Edge[(Maxn<<1)+5];
int tot,Head[Maxn+5];

inline void Addedge(int u,int v,int w)//加边操作 
{
    Edge[++tot].to=v;
    Edge[tot].nxt=Head[u];
    Edge[tot].w=w;
    Head[u]=tot;
}

//===========找重心 & 更新距离==========

int n,q,root;
int siz[Maxn+5],maxs[Maxn+5];//siz:子树大小 maxs:最大儿子的大小
int vis[Maxn+5];//vis:代表是否删去 
int sum;//sum:记录当前子树大小 

void getroot(int x,int f)//找重心 
{
    siz[x]=1;
    maxs[x]=0;
    for(register int i=Head[x];i;i=Edge[i].nxt)
    {
        int v=Edge[i].to;
        if(vis[v] || v==f) continue;
        getroot(v,x);
        siz[x]+=siz[v];
        maxs[x]=max(maxs[x],siz[v]);
    }
    maxs[x]=max(maxs[x],sum-siz[x]);
    root=maxs[x]<maxs[root]?x:root;
}

int dis[Maxn+5],now[Maxn+5],nowdis;
//dis:各结点到根结点的距离 now:存放这些距离 nowdis:计数器 

void getdis(int x,int f)
{
    now[++nowdis]=dis[x];
    for(register int i=Head[x];i;i=Edge[i].nxt)
    {
        int v=Edge[i].to;
        if(vis[v] || v==f) continue;
        dis[v]=dis[x]+Edge[i].w;
        getdis(v,x);
    }
} 

//================点分治==================

int Right;
int alive[Maxk+5];//alive:表示之前子树距离的个数 
stack<int> s;//使用栈统一处理 

void count(int x)//计算距离 
{
    for(register int i=Head[x];i;i=Edge[i].nxt)
    {
        int v=Edge[i].to;
        if(vis[v]) continue;
        nowdis=0;
        dis[v]=Edge[i].w;
        getdis(v,x);

        for(register int j=1;j<=nowdis;++j)
            if(q>=now[j])
                Right+=alive[q-now[j]];

        for(register int j=1;j<=nowdis;++j)//存放距离 
        {
            s.push(now[j]);
            alive[now[j]]++;
        }
    }
    while(!s.empty())//清空 
    {
        alive[s.top()]--;
        s.pop();
    }
}

void devide(int x)//点分治
{
    vis[x]=true;
    alive[0]=true;
    count(x);
    for(register int i=Head[x];i;i=Edge[i].nxt)
    {
        int v=Edge[i].to;
        if(vis[v]) continue;
        root=0;
        maxs[0]=sum=siz[v];
        getroot(v,0);
        getroot(root,0);
        devide(root);
    }
} 

int main()
{
    scanf("%d%d",&n,&q);
    for(register int i=1;i<n;++i)//连边 
    {
        int a,b;
        scanf("%d%d",&a,&b);
        Addedge(a,b,1);
        Addedge(b,a,1);
    }

    maxs[0]=sum=n;
    getroot(1,0);
    getroot(root,0);//找重心并更新子树大小 
    devide(root);

    printf("%d",Right);
    return 0;
}