Loading...

洛谷P5002 专心OI - 找祖先

check评论:0 条 remove_red_eye浏览量:340 change_historyTags:编程学习笔记
作者 : deco date_range日期 : 2018-12-22

一道比较水的树$dfs$题

我们来想一想,哪些点对$(x,y)$的最近公共祖先会是一个点$p$

$1.$ $x,y$处于$p$的不同子树内

$2.$ $x,y$中有一个是$p$

对于情况$1$,我们讲点$p$所有子树的$siz$两两相乘即可,但要注意不能枚举子树,会被那种$n-1$叉树卡死,答案为$\sum_{x\in P,y\in P,x\neq y} siz[x]*siz[y]$(设$p$所在的子树的结点集合为$P$)

对于情况$2$,有一个是点$p$,另一个点在其子树内,答案就是$siz[u]*2-1$(有一个点对为$(p,p)$,只能算一次)

然后$dfs$一遍就好了

代码${1:}$

#include <bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int n,r,m,fa[10010];
long long ans[10010],siz[10010];
vector<int> out[10010];
void dfs(int u)
{
    siz[u]=1;
    for(int i=0;i<out[u].size();i++)
    {
        int v=out[u][i];
        if(v==fa[u])
        {
            continue;
        }
        fa[v]=u;
        dfs(v);
        siz[u]+=siz[v];
    }
}
void makeans(int u)
{
    for(int i=0;i<out[u].size();i++)
    {
        for(int j=0;j<out[u].size();j++)
        {
            if(i==j)
            {
                continue;
            }
            int v1=out[u][i],v2=out[u][j];
            if(v1==fa[u])
            {
                break;
            }
            if(v2==fa[u])
            {
                continue;
            }
            ans[u]+=siz[v1]*siz[v2];
            ans[u]%=mod;
        }
    }
    ans[u]+=(siz[u]<<1)-1;
    ans[u]%=mod;
    for(int i=0;i<out[u].size();i++)
    {
        int v=out[u][i];
        if(v==fa[u])
        {
            continue;
        }
        makeans(v);
    }
}
int main()
{
    cin>>n>>r>>m;
    for(int i=1;i<n;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        out[x].push_back(y);
        out[y].push_back(x);
    }
    dfs(r);
    makeans(r);
    for(int i=1;i<=m;i++)
    {
        int x;
        scanf("%d",&x);
        printf("%d\n",ans[x]);
    }
}

很明显,这种会被$n-1$叉树卡死,我们需要优化

注意到乘法分配律,有$ab+bc=(a+c)b$,很显然,在第一种情况中,每一个子树会和其他所有子树都乘一遍,所以我们对于每个子树,直接用它的$siz$乘上总$siz$减去它的$siz$再$-1$的差即可

代码${2:}$

#include <bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int n,r,m,fa[10010];
long long ans[10010],siz[10010];
vector<int> out[10010];
void dfs(int u)
{
    siz[u]=1;
    for(int i=0;i<out[u].size();i++)
    {
        int v=out[u][i];
        if(v==fa[u])
        {
            continue;
        }
        fa[v]=u;
        dfs(v);
        siz[u]+=siz[v];
    }
}
void makeans(int u)
{
    for(int i=0;i<out[u].size();i++)
    {
        int v=out[u][i];
        if(v==fa[u])
        {
            continue;
        }
        ans[u]+=siz[v]*(siz[u]-siz[v]-1);
        ans[u]%=mod;
    }
    ans[u]+=(siz[u]<<1)-1;
    ans[u]%=mod;
    for(int i=0;i<out[u].size();i++)
    {
        int v=out[u][i];
        if(v==fa[u])
        {
            continue;
        }
        makeans(v);
    }
}
int main()
{
    cin>>n>>r>>m;
    for(int i=1;i<n;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        out[x].push_back(y);
        out[y].push_back(x);
    }
    dfs(r);
    makeans(r);
    for(int i=1;i<=m;i++)
    {
        int x;
        scanf("%d",&x);
        printf("%d\n",ans[x]);
    }
}

chevron_left 凸包学习笔记

暂无评论

正在回复给  
去登陆?

   点击刷新验证码

标签云

文章留名