![:(](./images/smilies/icon_frown.gif)
Code: Select all
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <memory.h>
#define MAX 10010
using namespace std;
int root, N, ansnum;
int ans[MAX], outdeg[MAX], C[MAX], W[MAX], path[MAX];
bool isfind[MAX];
vector<int>adj[MAX];
int dp(int now)
{
//a leaf node
if(outdeg[now]==0)
return W[now];
//if is found
if(isfind[now]) return C[now];
//top-down
int i, next, w, best;
for(i=0; i<(int)adj[now].size(); i++)
{
next = adj[now][i];
//if(next==parent)continue;
w = dp(next);
if(i==0 || w>best)
best = w, path[now] = next;
else if(w==best)
path[now] = max(path[now], next);
}
if( adj[now].size()==0 ) best = 0;
C[now] = W[now] + best;
//memorized
isfind[now] = true;
return C[now];
}
int main()
{
//freopen("4267", "r", stdin);
int i, j, k, c, datacase, cost;
scanf("%d", &datacase);
while(datacase--)
{
//clear the data
for(i=0; i<MAX; i++) adj[i].clear();
scanf("%d %d", &N, &root);
//read the tree information
memset(outdeg, 0, sizeof(outdeg));
for(i=0; i<N; i++)
{
scanf("%d %d", &W[i], &j);
//the children of node number i
for(k=0; k<j; k++)
{
scanf("%d", &c);
adj[i].push_back(c);
outdeg[i]++;
//adj[c].push_back(i);
}
}
//start to find the path and max-cost path
for(i=0; i<MAX; i++)
isfind[i] = false, C[i] = 0, path[i] = -1;
cost = dp(root);
printf("%d", cost);
//find the path (root to leaf)
ansnum = 0, ans[ansnum++] = root;
while(path[root]!=-1)
{
ans[ansnum++] = path[root];
root = path[root];
}
for(i=0; i<ansnum; i++)
{
if(i%10==0)
printf("\n%d", ans[i]);
else
printf(" %d", ans[i]);
}
putchar('\n');
}
return 0;
}