【HDU 2196】 Computer(树的直径)

题链http://acm.hdu.edu.cn/showproblem.php?pid=2196

这题可以用树形DP解决，自然也可以用最直观的方法解，先求出树的直径，那么树的任意节点的最远点必然是直径上的两个端点之一，证明可以通过反证法构造：

设端点为a,b;设任意点为i,假设存在一点c到i的距离大鱼i到a,b的距离，那么a与c又能形成一个距离更长的点对，与ab是直径的假设不符，因此不存在c，证明完成。

#include <queue>

#include <cmath>

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <iostream>

#include <algorithm>

#include <vector>

#define ll long long

#define inf 10000000000000

#define mod 1000000007

using namespace std;

ll read()

{

    ll x=0,f=1;

    char ch=getchar();

    while(ch<'0'||ch>'9')

    {

        if(ch=='-')f=-1;

        ch=getchar();

    }

    while(ch>='0'&&ch<='9')

    {

        x=x*10+ch-'0';

        ch=getchar();

    }

    return x*f;

}

const int N=1e4+10;

const int M=2e4+10;

struct Edge{

    int cost,to,nxt;

}Path[M];

int last[N],cnt;

void Addedge(int u,int v,int w){

    Path[cnt]=(Edge){w,v,last[u]};

    last[u]=cnt++;

}

int q[N*2],d[N],X;

void bfs(int x)

{

	X=0;

	int head=0,tail=1;

	q[0]=x;

	memset(d,0,sizeof(d));

	d[x]=1;

	while(head!=tail){

		int cur=q[head];

		head++;

		if(d[cur]>d[X]) X=cur;

		for(int i=last[cur];i;i=Path[i].nxt){

		    int v=Path[i].to;

			if(!d[v]&&v!=x){

				d[v]=d[cur]+Path[i].cost;

				q[tail++]=v;

			}

		}

	}

}

void Init()

{

    memset(last,0,sizeof(last));

    cnt=1;

}

int d2[N];

int main()

{

    int n;

    while(~scanf("%d",&n)){

        Init();

        for(int v=2;v<=n;v++){

            int u=read(),w=read();

            Addedge(u,v,w);

            Addedge(v,u,w);

        }

        bfs(1);int ans1=X;

        bfs(X);int ans2=X;

        for(int i=1;i<=n;i++) d2[i]=d[i]-1;

        bfs(X);

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

            printf("%d\n",max(d[i]-1,d2[i]));

        }

    }

    return 0;

}

巴特西

【HDU 2196】 Computer(树的直径)

【HDU 2196】 Computer(树的直径)

最新文章

热门文章