洛谷 P2195 HXY造公园 题解【树的直径】【并查集】【贪心】

点击量：165

   严重吐槽题面。。。

目录

题目描述

现在有一个现成的公园，有n个休息点和m条双向边连接两个休息点。众所周知，HXY是一个SXBK的强迫症患者，所以她打算施展魔法来改造公园并即时了解改造情况。她可以进行以下两种操作：

 

1、对某个休息点x，查询公园中所有经过该休息点的（应该删掉）路径中的最长路径。

 

2、对于两个休息点x、y，如果x，y已经可以互相到达则忽略此次操作。否则，在x可到达的所有休息点和y可到达的所有休息点（包括x，y自身）分别选择一个休息点，然后在这两个休息点之间连一条边，并且这个选择应该满足对于连接后的公园，x和y所在的区域（即x，y可达到的所有休息点和边组成的集合）中的最长路径的长度最小。

 

HXY打算进行q个操作，请你回答她的对于公园情况的询问（操作1）或者执行她的操作（操作2）。

 

注：所有边的长度皆为1。保证不存在环。最长路径定义为：对于点v1,v2……vk，如果对于其中任意的vi和vi+1(1<=i<=k-1)，都有边相连接，那么vj(1<=j<=k)所在区域的最长路径就是k-1。

 

输入输出格式

输入格式：

第一行，三个正整数，分别为n，m，q。

 

接下来的m行，每一行有两个正整数xi，yi，表示xi和yi有一条双向边相连。

 

再接下来的q行，每一行表示一个操作。

 

若该行第一个数为1，则表示操作1，之后还有一个正整数xi，表示要查询的休息点。

 

若该行第一个数为2，则表示操作2，之后还有两个正整数xi，yi，表示需要执行操作的两个休息点。

 

输出格式：

输出行数为操作1的个数。

 

每行输出对于操作1询问的回答。

 

输入输出样例

输入样例#1：

6 0 6

2 1 2

2 3 4

2 5 6

2 3 2

2 5 3

1 1

输出样例#1：

4

说明

数据范围：

对于10%的数据，只存在操作1。

 

对于30%的数据，1<=m<n<=20,1<=q<=5。

 

对于60%的数据，1<=m<n<=2000,1<=q<=1000。

 

对于100%的数据，1<=m<n<=3*10^5,1<=q<=3*10^5。

前言：

   机房考试的时候比较着急把题目看错了，以为第一问是直接求树的直径但是标程就是求树的直径啊！，还把两棵树的直径拼了半天最后挂成30分。下来之后yyx锯佬跟我说题意要求x点到直径较远端点的距离，以为是题意读错了。后来看到网上全都写的求直径就知道是题面错了。

尬

题解：

   首先，给出一个森林，预处理出每棵树的直径。在直径拼接时，要求新树的直径最小。可以发现，新树的直径是由原树1的u点和原树2的v点添加一条边，它们分别到自己子树中最远距离之和再加上这条边就是直径了。而要保证到自己子树最远距离之和最小，就是都要最小，就要在选择u和v上做文章。

   因为从树上一个点能遍历到最远的地方一定是直径的一个端点（贪心+树的直径求法），所以到子树最远距离最小的点，就是直径的中点。下证直径中点比树上任何一点都优，设中点到直径两端的距离分别为$ d_1,d_2$，则$ |d_2-d_1|\le 1$，此时答案为$ \max \{d_1,d_2 \}=\lceil \frac d2 \rceil$($ d$为直径)。因此直径上只要不是中点的点，$ d_1,d_2$的差值就会达到2或以上，此时就不能保证$ \max \{ d_1,d_2\}$最小了。而不在直径上的点一定有一条路径能到达直径上，那么此时的答案就是$ \max \{ d_1+\Delta x,d_2+\Delta x\} =\max \{ d_1,d_2 \} +\Delta x\} $，也就一定比$ \max \{ d_1,d_2\}$大。

   这样知道了要把两棵树直径的中点连接起来，就要算直径了。而算直径其实不用特别麻烦，只要知道两条直径的长度就可以求解。因为其中一条直径总是$ \lceil \frac {d_1}2 \rceil $，另一条总是$ \lceil \frac {d_2}2 \rceil $，那么合计加上连接的一条边就是$ \lceil \frac {d_1}2 \rceil +1+\lceil \frac {d_2}2 \rceil $。但是当$ d_1$较大，而$ d_2$较小时直径长仍然是$ d_1$，因为合并后$ \lceil \frac {d_1}2 \rceil +1+\lceil \frac {d_2}2 \rceil \le d_1$，$ d_1$仍然是最长链。因此我们只需要知道两棵树的直径，在合并它们时只用套公式$ d’ =\max \{ \lceil \frac {d_1}2 \rceil +1+\frac {d_2}2 , d_1,d_2 \}$就可以了。

    memset写错毁一生。。。蜜汁TLE

Code：

#include<cstdio>
#include<cstring>
int max(int x,int y)
{
    return x>y?x:y;
}
struct edge
{
    int n,nxt;
    edge(int n,int nxt)
    {
        this->n=n;
        this->nxt=nxt;
    }
    edge()
    {
        nxt=-1;
    }
}e[610000];
int head[301000],ecnt=-1;
void add(int from,int to)
{
    e[++ecnt]=edge(to,head[from]);
    head[from]=ecnt;
    e[++ecnt]=edge(from,head[to]);
    head[to]=ecnt;
}
int s[301000];
int my_find(int x)
{
    if(s[x]==x)
        return x;
    return s[x]=my_find(s[x]);
}
void my_union(int x,int y)
{
    s[my_find(y)]=my_find(x);
}
int d[301000],mx,tmp,dpt;
bool used[301000];
void dfs(int x)
{
    if(dpt>mx)
    {
        mx=dpt;
        tmp=x;
    }
    dpt++;
    for(int i=head[x];~i;i=e[i].nxt)
    {
        if(!used[e[i].n])
        {
            used[e[i].n]=true;
            dfs(e[i].n);
            used[e[i].n]=false;
        }
    }
    dpt--;
    return;
}
int main()
{
    memset(head,-1,sizeof(head));
    int n,m,q,u,v;
    scanf("%d%d%d",&n,&m,&q);
    for(int i=1;i<=n;i++)
        s[i]=i;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&u,&v);
        add(u,v);
        my_union(u,v);
    }
    for(int i=1;i<=n;i++)
        if(s[i]==i)
        {
            dpt=0;
            mx=-1;
            used[i]=true;
            dfs(i);//两边dfs求树的直径
            used[i]=false;
            mx--;
            int k=tmp;
            used[k]=true;
            dfs(k);
            used[k]=false;
            d[i]=mx;
        }
    int op;
    for(int i=1;i<=q;i++)
    {
        scanf("%d",&op);
        if(op==1)
        {
            scanf("%d",&u);
            printf("%d\n",d[my_find(u)]);
        }
        else
        {
            scanf("%d%d",&u,&v);
            u=my_find(u);
            v=my_find(v);
            if(u==v)
                continue;
            d[u]=max(max((d[u]+1>>1)+1+(d[v]+1>>1),d[u]),d[v]);
            my_union(u,v);//my_union时要记得是把v往u上并，或者先合并，最后再加my_find()
        }
    }
    return 0;
}