## 10672 - Marbles on a tree

Moderator: Board moderators

kamrul
New poster
Posts: 9
Joined: Sat Aug 24, 2002 11:21 am

### 10672 - Marbles on a tree

I used recursion to solve this problem. and it gives the solution to the test cases given in the problem perfectly. But i m getting WA .
can anyone tell me what's wrong with my code.
Code:
[cpp]
Code has been removed.
[/cpp]
Last edited by kamrul on Tue Jul 06, 2004 8:48 pm, edited 1 time in total.

Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
It seems that you assume that the root of the tree is always the node numbered 1, but that is wrong.
Your program fails on inputs where the root is not node 1,
like
2
1 0 0
2 2 1 1
0

Output should be 1.

kamrul
New poster
Posts: 9
Joined: Sat Aug 24, 2002 11:21 am

### Thanks:

Oh. That was a bad mistake.
Now i got AC

a.elbashandy
New poster
Posts: 12
Joined: Fri Dec 23, 2011 6:23 pm

### Re: 10672 - Marbles on a tree

I'm getting WA, are there any critical test cases to test my code ?

Code: Select all

``````removed after accepted
``````
Last edited by a.elbashandy on Sat Mar 23, 2013 1:07 pm, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 10672 - Marbles on a tree

Check input and AC output for thousands of problems on uDebug!

a.elbashandy
New poster
Posts: 12
Joined: Fri Dec 23, 2011 6:23 pm

### Re: 10672 - Marbles on a tree

thanks brianfry713

kakaroto2
New poster
Posts: 2
Joined: Sat Dec 07, 2013 5:30 am

### Re: 10672 - Marbles on a tree

Here's my code.

Code: Select all

``````#include<cstdio>
#include<cmath>
#include<vector>
using namespace std;

int main()
{
int n;
while( ~scanf("%d",&n)&&n )
{
int father,value,nkid;
int iskid[10005]={0};
int marble[10005]={0};
vector<vector<int> >tree;
tree.clear() , tree.resize(n);
for(int i=0;i<n;i++)
{
scanf("%d%d%d",&father,&value,&nkid);
marble[father-1]=value-1;
int kid;
for(int j=0;j<nkid;j++)
{
scanf("%d",&kid);
tree[father-1].push_back(kid-1);
iskid[kid-1]=1;
}
}
int root=-1;
for(int i=0;i<n;i++)
{
if( !iskid[i] )
{
root=i;
break;
}
}
int cnt=0;
for(int i=0;i<n;i++)
{
if(i==root)
continue;
int marbles=marble[i];
int k=tree[i].size();
for(int j=0;j<k;j++)
{
marbles+=marble[ tree[i][j] ];
}
cnt+=abs(marbles);
}
printf("%d\n",cnt);
}
return 0;
}``````
I don't use DFS,but I realize that 1 isn't neccessarily the root.
So I search for it,and pass several special inputs,but still got a'WA'.
HELP ME!!!

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 10672 - Marbles on a tree

Input:

Code: Select all

``````4
1 2 1 2
2 1 1 3
3 1 1 4
4 0 0
``````
AC output 3
Check input and AC output for thousands of problems on uDebug!

kakaroto2
New poster
Posts: 2
Joined: Sat Dec 07, 2013 5:30 am

### Re: 10672 - Marbles on a tree

brianfry713 wrote:Input:

Code: Select all

``````4
1 2 1 2
2 1 1 3
3 1 1 4
4 0 0
``````
AC output 3
thx!
I've already figure out that my algo will fail when the depth of the tree is more than 3.
So I compromise to Dfs,and then Ac in 25ms.
Thanks again for brianfry713's test sample!