HDU2196Computer(树形dp)

/********************************************************
Problem : 2196 ( Computer )     Judge Status : Accepted
RunId : 15495812    Language : G++    Author : G_lory
********************************************************/
#include

using namespace std;

const int N = 100005;

vector G[N];
vector L[N];

int dis1[N];
int dis2[N];

int len;
int fa, fb;

void dfs(int pre, int v, int d[], int x)
{
    d[v] = x;
    for (int i = 0; i  len)
    {
        len = x;
        fa = v;
    }
}

int main()
{
    std::ios::sync_with_stdio(false);
    int n;
    int a, b;
    while (cin >> n)
    {
        for (int i = 0; i <= n; ++i)
        {
            G[i].clear();
            L[i].clear();
        }
        for (int i = 2; i <= n; ++i)
        {
            cin >> a >> b;
            G[a].push_back(i);
            G[i].push_back(a);
            L[a].push_back(b);
            L[i].push_back(b);
        }

        len = -1;
        dfs(-1, 1, dis1, 0);
        len = -1;

        dfs(-1, fa, dis1, 0);
        len = -1;
        dfs(-1, fa, dis2, 0);
        for (int i = 1; i <= n; ++i)
        {
            cout <

/****************************************************
Problem : 2196 ( Computer )     Judge Status : Accepted
RunId : 15496928    Language : G++    Author : G_lory
****************************************************/
#include 

using namespace std;

const int N = 100005;

vector G[N];
vector L[N];

int dis[N];
int sdis[N];
int id[N];

void dfs(int v, int pre)
{
    for (int i = 0; i  dis[u])
            {
                sdis[u] = dis[u];
                dis[u] = L[v][i] + sdis[v];
                id[u] = v;
            }
            else if (L[v][i] + sdis[v] > sdis[u])
            {
                sdis[u] = L[v][i] + sdis[v];
            }
        }
        else
        {
            if (L[v][i] + dis[v] > dis[u])
            {
                sdis[u] = dis[u];
                dis[u] = L[v][i] + dis[v];
                id[u] = v;
            }
            else if (L[v][i] + dis[v] > sdis[u])
            {
                sdis[u] = L[v][i] + dis[v];
            }
        }
        dfs1(u, v);
    }
}

int main()
{
    std::ios::sync_with_stdio(false);
    int n;
    int a, b;
    while (cin >> n)
    {
        memset(dis, 0, sizeof dis);
        memset(sdis, 0, sizeof sdis);
        for (int i = 0; i <= n; ++i)
        {
            G[i].clear();
            L[i].clear();
        }
        for (int i = 2; i <= n; ++i)
        {
            cin >> a >> b;
            G[a].push_back(i);
            G[i].push_back(a);
            L[a].push_back(b);
            L[i].push_back(b);
        }
        dfs(1, -1);
        dfs1(1, -1);
        for (int i = 1; i <= n; ++i)
        {
            cout <