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

作者: wjyyy 分类: 并查集,树的直径,解题报告,贪心 发布时间: 2018-07-13 08:07

点击量:18

 

   严重吐槽题面。。。

 

题目描述

现在有一个现成的公园,有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;
}

说点什么

avatar
  Subscribe  
提醒
/* */