题目描写叙述
给出一棵含有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;
}