CF911F Tree Destruction (树的直径,贪心)

题目链接

Solution

1.先找出树的直径.

2.遍历直径沿途的每一个节点以及它的子树.

3.然后对于每个非直径节点直接统计答案,令直径的两个端点为 \(x_1,x_2\) .

\[Ans=\sum{Max(dis(i,x1),dis(i,x2))}
\]

最后再单独把直径拎出来,单独统计一次就好了.

正确性证明:

redbag 一句话解决:

如果说这其中的某个答案不是最优,那么找的直径不就是错的么。

"跑的飞快。"

Code

#include<bits/stdc++.h>

using namespace std;

const int maxn=200008;

struct sj{

    int to,next;

}a[maxn*2];

int head[maxn],size,x,y,road[maxn];

int root,flag,n,cnt,far[5],kk,vis[maxn];

int dis[maxn][3],v[maxn],num;

long long ans;

int ans1[maxn],ans2[maxn],siz;

void add(int x,int y)

{

    a[++size].to=y;

    a[size].next=head[x];

    head[x]=size;

}

void dfs(int x)

{

    v[x]=1;

    if(cnt>kk)

    far[root==1?1:2]=x,kk=cnt;

    for(int i=head[x];i;i=a[i].next)

    {

        int tt=a[i].to;

        if(!v[tt])

            cnt++,dfs(tt);

    }

    v[x]=0; cnt--;

}

void fuck(int x)

{

     v[x]=1;

     if(x==far[2]){flag=1;}

     for(int i=head[x];i;i=a[i].next)

     {

     	int tt=a[i].to;

     	if(!v[tt])

     	fuck(tt);

     	if(flag){road[++num]=x;vis[x]=1;break;}

     }

     v[x]=0;

}

void getans(int x)

{

    v[x]=1;

    for(int i=head[x];i;i=a[i].next)

    {

        int tt=a[i].to;

        if(!v[tt]&&!vis[tt])

            getans(tt),ans+=max(dis[tt][1],dis[tt][2]);

    }

    if(dis[x][1]>dis[x][2])

    ans1[++siz]=far[1];

    else ans1[++siz]=far[2];

    ans2[siz]=x;

    v[x]=0;

}

void getdis(int x,int to)

{

    v[x]=1;

    for(int i=head[x];i;i=a[i].next)

    {

        int tt=a[i].to;

        if(!v[tt])

        {dis[tt][to]=dis[x][to]+1; getdis(tt,to);}

    }

    v[x]=0;

}

int main()

{

    cin>>n;

    for(int i=1;i<n;i++)

    {

         scanf("%d%d",&x,&y),

         add(x,y), add(y,x);

    }

    root=1; dfs(root);

    root=far[1]; kk=0;

    cnt=0;  dfs(root);

    fuck(root);

    getdis(far[1],1); getdis(far[2],2);

    for(int i=2;i<num;i++)

    getans(road[i]),siz--;

    for(int i=1;i<=kk;i++)ans+=i;

    cout<<ans<<endl;

    for(int i=1;i<=siz;i++)

    cout<<ans1[i]<<' '<<ans2[i]<<' '<<ans2[i]<<endl;

    for(int i=1;i<num;i++)

    cout<<far[1]<<' '<<road[i]<<' '<<road[i]<<endl;

}

巴特西

CF911F Tree Destruction (树的直径,贪心)

题目链接

Solution

Code

最新文章

热门文章