【HDU 2196】 Computer (树形DP)

【HDU 2196】 Computer

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

刘汝佳《算法竞赛入门经典》P282页留下了这个问题：给出一棵树，求每个节点的最远点，每一个节点的最远点有两种可能，一种是向下拓展的最远点，一种是父节点的最远点，那么需要两次dfs即可。一次求出每个节点的最远点和次远点，一次直接计算。

#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=1e4+10;

struct Edge{

    int cost,to,nxt;

}Path[M];

int head[N],cnt;

ll dis[N];

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

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

    head[u]=cnt++;

}

void Init()

{

    memset(head,0,sizeof(head));

    cnt=1;

}

//dp[i][0],dp[i][1]表示向下最大和次大距离,dp[i][2]表示向上最大距离

int dp[N][3];

void dfs1(int u)

{

    int t1=0,t2=0;   //最大和次大

    for(int i=head[u];i;i=Path[i].nxt){

        int v=Path[i].to;

        dfs1(v);

        int tmp=dp[v][0]+Path[i].cost;

        if(t1<=tmp){

            t2=t1;t1=tmp;

        }

        else if(t2<tmp) t2=tmp;

    }

    dp[u][0]=t1;dp[u][1]=t2;

}

void dfs2(int u)

{

    for(int i=head[u];i;i=Path[i].nxt){

        int v=Path[i].to;

        dp[v][2]=max(dp[u][2],dp[v][0]+Path[i].cost==dp[u][0]?dp[u][1]:dp[u][0])+Path[i].cost;

        dfs2(v);

    }

}

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);

        }

        dfs1(1);dp[1][2]=0;dfs2(1);

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

            printf("%d\n",max(dp[i][0],dp[i][2]));

    }

    return 0;

}

巴特西

【HDU 2196】 Computer (树形DP)

【HDU 2196】 Computer

最新文章

热门文章