SDUT2013级測试赛_D

题目描写叙述

给出一棵含有n个点的树。每一个点权值为wi。求从根节点到叶子结点权值和最大的那条路经的权值和是多少。

输入

n(1<= n && n <= 10000)。

接下来n+1行，每行两个整数w(w
<= 1000)。

第i个节点的父节点为w，若 i为根节点。600组数据。

输出

对于每组数据，输出一个数代表答案。

演示样例输入

3

0 5

1 5

1 6

演示样例输出

11

提示

来源

解题报告

求从根节点出发到叶子的最长路。

。

。非常像数塔。。

。

我暴力dfs过了.怒搜全部数枝，搜完答案就有了。

。。

#include <iostream>

#include <cstdio>

#include <cstring>

using namespace std;

struct node

{

    int v,next;

} edge[100000];

int head[10010],cnt,vv[10010],vis[10010],n,maxx;

void add(int u,int v)

{

    edge[cnt].v=v;

    edge[cnt].next=head[u];

    head[u]=cnt++;

}

void dfs(int s,int d)

{

    int i,j;

    for(i=head[s]; i!=-1; i=edge[i].next)

        dfs(edge[i].v,d+vv[edge[i].v]);

    if(d>maxx)

        maxx=d;

}

int main()

{

    int i,j,v,w;

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

    {

        maxx=0;

        cnt=0;

        memset(edge,0,sizeof(edge));

        memset(vv,0,sizeof(vv));

        memset(head,-1,sizeof(head));

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

        {

            scanf("%d%d",&v,&w);

            add(v-1,i);

            vv[i]=w;

        }

        dfs(0,vv[0]);

        printf("%d\n",maxx);

    }

    return 0;

}

学长标程好像跟数塔类似，从下至上的找最大的。。

。

以下是啸爷的标程。。。

#include <algorithm>

#include <iostream>

#include <cstring>

#include <cstdlib>

#include <cstdio>

#include <queue>

#include <cmath>

#include <stack>

#include <map>

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

#define EPS (1e-8)

#define LL long long

#define ULL unsigned long long

#define _LL __int64

#define _INF 0x3f3f3f3f

#define Mod 9999991

using namespace std;

int head[10010];

struct E

{

    int v,next;

}edge[10010];

int Top;

int Link(int u,int v)

{

    edge[Top].v = v;

    edge[Top].next = head[u];

    head[u] = Top++;

}

int value[10010];

int dfs(int root)

{

    int temp = 0;

    for(int p = head[root];p != -1; p = edge[p].next)

    {

        temp = max(temp,dfs(edge[p].v));

    }

    value[root] += temp;

    return value[root];

}

int main()

{

    freopen("data1.in","r",stdin);

    freopen("data1.out","w",stdout);

    int n,i,j,v,w;

    while(scanf("%d",&n) != EOF)

    {

        memset(head,-1,sizeof(head));

        Top = 0;

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

        {

            scanf("%d %d",&v,&w);

            Link(v,i);

            value[i] = w;

        }

        printf("%d\n",dfs(1));

    }

    return 0;

}