【题目链接】:click here~~
【题目大意】:给你一棵树,在树上从根节点到叶子结点找一条结点权值最大的路径,并输出该条路径
【思路】:dfs搜索,递归查找权值,递归输出路径
代码 :
/*
* Problem: UVALive 4267
* Running time: 23MS
* Complier: G++
* Author: herongwei
* Create Time: 20:16 2015/10/14
*/
#include <stdio.h>
#include <string.h>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn=1e4+10;
const int inf=0x3f3f3f3f;
inline int max(int a,int b){return a>b?a:b;}
inline int min(int a,int b){return a<b?a:b;}
int w1[maxn],w2[maxn],a[maxn];
vector<int >G[maxn];
int n,m,len,ans;
int dfs(int root) //递归求根节点的权值
{
int cnt=0;
for(int i=0; i<G[root].size(); ++i)
{
cnt+=dfs(G[root][i]);
// cout<<"root= "<<root<<" "<<"i="<<i<<"G[root][i]= "<<" "<<G[root][i]<<endl;
}
w1[root]+=cnt;
//cout<<"cnt= "<<cnt<<endl;
return w1[root];
}
void dfss(int root)//递归求路径
{
a[len++]=root;
ans+=w2[root];
int ck=-1;
if(G[root].size()) ck=G[root][0];
for(int i=0; i<G[root].size(); ++i)
{
if(w1[G[root][i]]>w1[ck]) ck=G[root][i];
else if(w1[G[root][i]]==w1[ck]&&ck<G[root][i])
ck=G[root][i];
}
if(ck<0) return ;
else dfss(ck);
}
int main()
{
//freopen("1.txt","r",stdin);
int t;scanf("%d",&t);
while(t--)
{
len=0,ans=0;
int n,rt;scanf("%d%d",&n,&rt);
for(int i=0; i<n; ++i) G[i].clear();
for(int i=0; i<n; ++i)
{
int x,y;scanf("%d%d",&w1[i],&x);
while(x--)
{
scanf("%d",&y);
G[i].push_back(y);
}
}
for(int i=0; i<n; ++i) w2[i]=w1[i];
dfs(rt);
// cout<<w1[rt]<<endl;
dfss(rt);
printf("%d\n",ans);
for(int i=0; i<len-1; ++i)
{
printf("%d",a[i]);
if(i&&i%10==9) puts("");
else printf(" ");
}
printf("%d\n",a[len-1]);
}
return 0;
}