题解 P1395 【会议】

· · 题解

告诉你一个秘密，这其实是一道模拟题

解题方法/步骤：

一.初审题目：审清基本条件，目标

（1）可以通过“n-1条路径”，“联通”判断这是一棵树，“路径”可判断这是一棵无根树。

（2）“每条路径的长度都为1”降低了题目难度。

（3）“100%数据n<=50000”可判断该题算法时间复杂度为O（n）～O（nlogn）。

（4）“要把会议地点设置在哪个村民的家中，并且这个距离总和最小是多少？”可得目标。

二.初析题目：理清主要算法

1.设置地点方法

（1）既然此题给的是一棵无根树，不妨设1为根。

（2）不妨设1是我们要找的点;

如上图，如果将1改成2,会发生什么？1到会议的距离+1，2～9到会议的距离-1，所以2优于1。

（3）进一步分析，可以发现：如果节点从x到（child（x）），则有（以child（x）为根的子树）个点距离-1，其余点距离+1。

2.求路程方法

其实只要先预处理出其他点到1的距离，再在修改过程中更改即可。

至此，该题的主要算法就出来了。

三.再析题目：理清次要算法和优化技巧

（1）因为要预处理出以每个节点为根的子树的节点个数，所以这里建议用邻接表存树。代码如下：

void add(int a,int b)
{
    o++;
    to[o]=b;
    next[o]=first[a];
    first[a]=o;
    return;
}

（2）在节点转移时，其实只需要考虑节点最多的那棵子树就可以了。

整题代码如下：

# include <stdio.h>
int o,first[50010],next[100010],to[100010],zs[50010],zdz[50010],zds[50010],ans,ro[50010];
void add(int a,int b)
{
    o++;
    to[o]=b;
    next[o]=first[a];
    first[a]=o;
    return;
}
void jdgs(int a,int b)
{
    int i,j;
    zs[a]=1;
    for(i=first[a];i;i=next[i])
    {
        j=to[i];
        if(j==b)
            continue;
        jdgs(j,a);
        zs[a]+=zs[j];
        ro[a]+=ro[j];
    }
    for(i=first[a];i;i=next[i])
    {
        j=to[i];
        if(j==b)
            continue;
        if(zs[j]>zds[a])
        {
            zds[a]=zs[j];
            zdz[a]=j;
        }
        if(zs[j]==zds[a] && zdz[a]>j)
            zdz[a]=j;
    }
    ro[a]+=zs[a]-1;
    return;
}
int main()
{
    int i,j,n,m,a,b;
    scanf("%d",&n);
    for(i=1;i<n;i++)
    {
        scanf("%d%d",&a,&b);
        add(a,b);
        add(b,a);
    }
    jdgs(1,0);
    m=1;
    ans=ro[1];
    while(1)
    {
        if(zds[m]>(n-zds[m]) || zds[m]==(n-zds[m]) && m>zdz[m])
        {
            ans=ans+n-2*zds[m];
            m=zdz[m];
        }
        else
            break;
    }
    printf("%d %d",m,ans);
}

欢迎下次光临！