hdu2196树形dp

有一棵树，找每个节点所能到达的最远距离是多少

dis[u][0]正向最大距离 dis[u][1]正向次大距离 dis[u][2]反向最大距离

先一边dfs求出每个节点的正向最大距离（就是向下）和次向最大距离，以及longest记录下当前节点的正向最大距离路径的子节点（为了第二遍dfs，判断这一条路是不是正向最大距离）

再进行第二遍dfs，v是u 的子节点，如果v在u的正向最大距离路径里(即longest[u]=v)那么v的最大反向距离就是max（u的最大反向距离，u的正向次大距离）+w【u】【v】

如果v不在u 的正向最大距离路径里，那么v的最大反向距离就是max（u的最大反向距离，u的正向最大距离）+w【u】【v】

#include<map>

#include<set>

#include<cmath>

#include<queue>

#include<stack>

#include<vector>

#include<cstdio>

#include<cassert>

#include<iomanip>

#include<cstdlib>

#include<cstring>

#include<iostream>

#include<algorithm>

#define pi acos(-1)

#define ll long long

#define mod 1000000007

#define ls l,m,rt<<1

#define rs m+1,r,rt<<1|1

#pragma comment(linker, "/STACK:1024000000,1024000000")

using namespace std;

const double g=10.0,eps=1e-;

const int N=+,maxn=+,inf=0x3f3f3f;

struct edge{

    int to,Next,w;

}e[N*];

int cnt,Head[N];

int longest[N],dis[N][];//0正向最大距离，1正向次大距离，2反向最大距离

void add(int u,int v,int w)

{

    e[cnt].to=v;

    e[cnt].w=w;

    e[cnt].Next=Head[u];

    Head[u]=cnt++;

}

int dfs1(int u,int fa)//返回u的正向最大距离,fa是u的父节点

{

    if(dis[u][]>)return dis[u][];

    dis[u][]=dis[u][]=dis[u][]=longest[u]=;

    for(int i=Head[u];~i;i=e[i].Next)

    {

        int v=e[i].to;

        if(v==fa)continue;

        if(dis[u][]<dfs1(v,u)+e[i].w)//v是u的最大距离中的一个子节点

        {

            longest[u]=v;

            dis[u][]=max(dis[u][],dis[u][]);//此时dis[u][0]就是一个可能的次大节点了

            dis[u][]=dfs1(v,u)+e[i].w;

        }

        else if(dis[u][]<dfs1(v,u)+e[i].w)

            dis[u][]=max(dis[u][],dfs1(v,u)+e[i].w);

    }

    return dis[u][];

}

int dfs2(int u,int fa)

{

    for(int i=Head[u];~i;i=e[i].Next)

    {

        int v=e[i].to;

        if(v==fa)continue;

        if(longest[u]==v)dis[v][]=max(dis[u][],dis[u][])+e[i].w;

        else dis[v][]=max(dis[u][],dis[u][])+e[i].w;

        dfs2(v,u);

    }

}

int main()

{

    ios::sync_with_stdio(false);

    cin.tie();

    int n;

    while(cin>>n){

        cnt=;

        memset(Head,-,sizeof Head);

        memset(dis,-,sizeof dis);

        memset(longest,-,sizeof longest);

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

        {

            int v,w;

            cin>>v>>w;

            add(i,v,w);

            add(v,i,w);

        }

        dfs1(,-);

        dfs2(,-);

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

            cout<<max(dis[i][],dis[i][])<<endl;

    }

    return ;

}

/*

longest[i]=j代表i在子树中的最大距离经过了j节点

*/

树形dp

巴特西

hdu2196树形dp

最新文章

热门文章