## 10459 - The Tree Root

All about problems in Volume 104. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

prashantharshi
New poster
Posts: 22
Joined: Wed May 21, 2014 10:16 am

### Re: 10459 - The Tree Root

i m getting WA contnuously even my code print correct answers
need help
#include<iostream>
#define max 5100
#define size 5100
int pred[max];
int status[max];
int height[max];
int state[max];
using namespace std;
struct node
{
int data;
node(int d)
{
data=d;
}
};
struct lnode
{
int d;
node* right;
lnode* down;
lnode(int k)
{
d=k;
right=NULL;
down=NULL;
}
};

struct tnode
{
int data;
int no;
int flag;
tnode** childlist;
tnode(int d)
{
data=d;
no=0;
flag=0;
}
};
struct stack
{
tnode* arr[size];
int top;
void push(tnode*);
tnode* pop();
stack()
{
top=-1;
}
}st;
void stack::push(tnode* ptr)
{
arr[++top]=ptr;
}
tnode* stack::pop()
{
tnode* p1=arr[top];
top--;
return p1;
}
struct queue
{
int front;
int rear;
tnode* arr[size];
void insert(tnode*);
tnode* del();
queue();
}q;
queue::queue()
{
front=-1;
rear=-1;
}
tnode* queue::del()
{

if(front!=-1)
{
tnode* f=arr[front];
if(front==rear)
{
front=-1;
rear=-1;
}
else
{
front=(front+1)%size;
}
return f;
}

}
void queue::insert(tnode* f)
{
rear=(rear+1)%size;
arr[rear]=f;
if(front==-1)
front=0;
}

void fun(tnode* &root,int v,int n)
{
if(!root)
{
root=new tnode(v);
}
int loc[max];
int k,cnt;
k=cnt=0;
for(int i=1;i<=n;i++)
{
if(pred==v)
{
loc[k]=i;
cnt++;
k++;
}
}
root->no=cnt;
root->childlist=new tnode*[cnt];
for(int i=0;i<cnt;i++)
{
root->childlist=NULL;;
}
for(int i=0;i<cnt;i++)
{
fun(root->childlist,loc,n);
}
}
void replicate(tnode* root,tnode* &ptr)
{
if(!ptr)
{
ptr=new tnode(root->data);
ptr->no=root->no;
ptr->childlist=new tnode*[ptr->no];
for(int i=0;i<ptr->no;i++)
{
ptr->childlist=NULL;
}
}
for(int i=0;i<ptr->no;i++)
{
replicate(root->childlist,ptr->childlist);
}

}
int cnt_ancestor(tnode* root,int k,int &cnt)
{
int k1;
if(root->data==k)
{
root->flag=1;
return 1;
}
for(int i=0;i<root->no;i++)
{
k1=cnt_ancestor(root->childlist,k,cnt);
if(k1)
{
root->flag=1;
cnt++;
return 1;
}
}
return 0;
}
tnode* make_root(tnode* root,int cnt)
{
if(cnt==0)
return root;
tnode* ptr;
int p,ind,i;
while(cnt!=0)
{
for(i=0;i<root->no;i++)
{
if(root->childlist->flag==1)
{
ind=i;
ptr=root->childlist;
}
}
for(i=0;i<ptr->no;i++)
{
q.insert(ptr->childlist[i]);
}
p=ptr->no;
ptr->no++;
ptr->childlist=new tnode*[ptr->no];
for(i=0;i<p;i++)
{
ptr->childlist[i]=q.del();
}
ptr->childlist[i]=root;
for(i=ind;i<(root->no)-1;i++)
{
root->childlist[i]=root->childlist[i+1];
}
root->childlist[i]=NULL;
root->no--;
root->flag=0;
root=ptr;
cnt--;
}
return ptr;
}
void display(tnode* root)
{
if(root->no==0)
{
cout<<root->data<<" ";
return;
}
else
{
cout<<root->data<<" ";
for(int i=0;i<root->no;i++)
{
display(root->childlist[i]);
}
}
}
int get_height(tnode* root)
{
int m=0;
if(root->no==0)
{
return 0;
}
else
{
for(int i=0;i<root->no;i++)
{
int k=1+get_height(root->childlist[i]);
if(k>m)
m=k;
}
}
return m;
}
lnode* addafter1(lnode* start,int d)
{
if(start==NULL)
{
start=new lnode(d);
return start;
}
lnode* temp=start;
while(temp->down!=NULL)
{
temp=temp->down;
}
temp->down=new lnode(d);
return start;
}
node* addafter2(node* strt,int d)
{
if(strt==NULL)
{
strt=new node(d);
return strt;
}
node* temp=strt;
{
}
return strt;
}
lnode* get_address(lnode* start,int v)
{
lnode* temp=start;
while(temp->d!=v)
{
temp=temp->down;
}
return temp;
}
void dfs(lnode* start,int v)
{
state[v]=1;
node* temp=ptr->right;
while(temp!=NULL)
{
int p=temp->data;
if(state[p]==0)
{
pred[p]=v;
dfs(start,p);
}
}
}
int main()
{
lnode* start=NULL;
int n,p,k,cnt;
int bh=999999;
int wh=-9999;
tnode** ptr;
tnode* root=NULL;
lnode* temp;
cin>>n;
ptr=new tnode*[n+1];
for(int i=1;i<=n;i++)
{
ptr[i]=NULL;
pred[i]=-1;
status[i]=0;
state[i]=0;
}
for(int i=1;i<=n;i++)
{
temp=start;
while(temp->down!=NULL)
{
temp=temp->down;
}
cin>>p;
for(int j=0;j<p;j++)
{
cin>>k;
}
}
dfs(start,1);
fun(root,1,n);
for(int i=1;i<=n;i++)
{
replicate(root,ptr[i]);
cnt=0;
int c=cnt_ancestor(ptr[i],i,cnt);
ptr[i]=make_root(ptr[i],cnt);
height[i]=get_height(ptr[i]);

}
for(int i=1;i<=n;i++)
{
if(height[i]<bh)
{
bh=height[i];
}
}
cout<<"Best Roots : ";
for(int i=1;i<=n;i++)
{
if(height[i]==bh)
cout<<i<<" ";
}
cout<<"\n";
for(int i=1;i<=n;i++)
{
if(height[i]>wh)
{
wh=height[i];
}
}
cout<<"Worst Roots : ";
for(int i=1;i<=n;i++)
{
if(height[i]==wh)
cout<<i<<" ";
}
return 0;

}

prashantharshi
New poster
Posts: 22
Joined: Wed May 21, 2014 10:16 am

### Re: 10459 - The Tree Root

here is my revised code using just dfs on adjacency list and getting the maximum depth during dfs as the height when that vertex act as root
my code is giving perfect outupts stiil verdict is WA
need urgent help
#include<iostream>
#define max 5100
int state[max];
int height[max];
using namespace std;
struct node
{
int data;
node(int d)
{
data=d;
}
};
struct lnode
{
int d;
node* right;
lnode* down;
lnode(int k)
{
d=k;
right=NULL;
down=NULL;
}
};

lnode* addafter1(lnode* start,int d)
{
if(start==NULL)
{
start=new lnode(d);
return start;
}
lnode* temp=start;
while(temp->down!=NULL)
{
temp=temp->down;
}
temp->down=new lnode(d);
return start;
}
node* addafter2(node* strt,int d)
{
if(strt==NULL)
{
strt=new node(d);
return strt;
}
node* temp=strt;
{
}
return strt;
}
lnode* get_address(lnode* start,int v)
{
lnode* temp=start;
while(temp->d!=v)
{
temp=temp->down;
}
return temp;
}
void reset_status(int n)
{
for(int i=1;i<n;i++)
{
state=0;
}
}
void dfs(lnode* start,int v,int h,int &m)
{
state[v]=1;
node* temp=ptr->right;
while(temp!=NULL)
{
int p=temp->data;
if(state[p]==0)
{
dfs(start,p,h+1,m);
}
}
if(h>m)
m=h;
}
int main()
{
lnode* start=NULL;
int h,m,n,p,k;
int bh=999999;
int wh=-9999;
lnode* temp;
cin>>n;
for(int i=1;i<=n;i++)
{
temp=start;
while(temp->down!=NULL)
{
temp=temp->down;
}
cin>>p;
for(int j=0;j<p;j++)
{
cin>>k;
}
}
for(int i=1;i<=n;i++)
{
h=0,m=0;
reset_status(n);
dfs(start,i,h,m);
height=m;
}
for(int i=1;i<=n;i++)
{
if(height<bh)
{
bh=height;
}
}
cout<<"Best Roots : ";
for(int i=1;i<=n;i++)
{
if(height==bh)
cout<<i<<" ";
}
cout<<"\n";
for(int i=1;i<=n;i++)
{
if(height>wh)
{
wh=height;
}
}
cout<<"Worst Roots : ";
for(int i=1;i<=n;i++)
{
if(height==wh)
cout<<i<<" ";
}
return 0;

}

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

### Re: 10459 - The Tree Root

I ran your code on the sample input. Your code is printing:

Code: Select all

``````Best Roots : 1
Worst Roots : 4 5 6 7 ``````
You also have an extra space at the end of each line. The correct sample output is:

Code: Select all

``````Best Roots  : 1
Worst Roots : 4 5 6 7``````
Use the code blocks when posting code.
Check input and AC output for thousands of problems on uDebug!

piyukr
New poster
Posts: 17
Joined: Sun Jan 26, 2014 10:35 am

### Re: 10459 - The Tree Root

How to find the best roots for this problem?

lighted
Guru
Posts: 585
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

### Re: 10459 - The Tree Root

Sample Output

Best Rootsbb: 1
Worst Rootsb: 4 5 6 7
b is space.
brianfry713 wrote:Input:

Code: Select all

``````7
2 2 3
3 1 6 7
3 1 4 5
1 3
1 3
1 2
1 2
7
2 2 3
3 1 6 7
3 1 4 5
1 3
1 3
1 2
1 2``````
Output should be:

Code: Select all

``````Best Roots : 1
Worst Roots : 4 5 6 7
Best Roots : 1
Worst Roots : 4 5 6 7``````
brianfry713 wrote:I ran your code on the sample input. Your code is printing:

Code: Select all

``````Best Roots : 1
Worst Roots : 4 5 6 7 ``````
You also have an extra space at the end of each line. The correct sample output is:

Code: Select all

``````Best Roots  : 1
Worst Roots : 4 5 6 7``````
Use the code blocks when posting code.
They differ in one space after Best Roots. Is sample output correct?
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

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

### Re: 10459 - The Tree Root

The sample output is correct, there should be two spaces after Best Roots. I edited my previous post.
Check input and AC output for thousands of problems on uDebug!

lighted
Guru
Posts: 585
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

### Re: 10459 - The Tree Root

piyukr wrote:How to find the best roots for this problem?
The way how I find best roots:
1. Do loop while nodes exits
2. In each step delete all nodes that have only one parrent.
3. Nodes which remain at last are best roots.

I read that in a tree remain 1 or 2 node. As i understood they are called centers of tree(or graph).

I joined input given in this thread.

Code: Select all

``````7
2 2 3
3 1 6 7
3 1 4 5
1 3
1 3
1 2
1 2

8
0
0
1 5
1 5
2 3 4
2 8 5
1 8
2 7 6

9
2 3 2
3 4 5 1
3 6 7 1
3 8 9 2
1 2
1 3
1 3
1 4
1 4

8
3 3 4 2
2 5 1
1 1
2 6 1
1 2
3 8 7 4
1 6
1 6

7
2 2 3
3 1 6 7
3 1 4 5
1 3
1 3
1 2
1 2``````
Acc output

Code: Select all

``````Best Roots  : 1
Worst Roots : 4 5 6 7
Best Roots  : 6
Worst Roots : 3 4 7
Best Roots  : 1 2
Worst Roots : 6 7 8 9
Best Roots  : 1 4
Worst Roots : 5 7 8
Best Roots  : 1
Worst Roots : 4 5 6 7
``````
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

Farsan
New poster
Posts: 34
Joined: Fri Aug 12, 2011 6:37 am

### Re: 10459 - The Tree Root

Is the given tree connected or could there be any forest???Getting Wa... Passed all I/O of the forum when the tree is connected,here is my code

Code: Select all

``````//ACED
``````
Last edited by Farsan on Thu Sep 11, 2014 9:19 am, edited 1 time in total.

lighted
Guru
Posts: 585
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

### Re: 10459 - The Tree Root

Your program doen't pass second test posted above.

Input

Code: Select all

``````8
0
0
1 5
1 5
2 3 4
2 8 5
1 8
2 7 6
``````
Acc Output

Code: Select all

``````Best Roots  : 6
Worst Roots : 3 4 7``````

Code: Select all

``````Best Roots  : 1 2 3 4 5 6 7 8
Worst Roots :``````
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

Farsan
New poster
Posts: 34
Joined: Fri Aug 12, 2011 6:37 am

### Re: 10459 - The Tree Root

That's why i asked whether is it possible that there is a forest instead of a tree in input.Even your output differs from the output i got herehttp://www.udebug.com/UVa/10459... I do not think there is any input where any node is isolated.

lighted
Guru
Posts: 585
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

### Re: 10459 - The Tree Root

Yes, you are right. According to problem description
Then successively for each i'th node there will be a positive integer K following id of K nodes which are adjacent to i

I added 1st and 2nd node to the tree. Try input

Code: Select all

``````8
1 5
1 8
1 5
1 5
4 3 4 1 6
2 8 5
1 8
3 7 6 2``````
Acc. Output

Code: Select all

``````Best Roots  : 6
Worst Roots : 1 2 3 4 7``````

Code: Select all

``````Best Roots  : 6
Worst Roots : 2 7``````
Output of forthright48 (uDebug)

Code: Select all

``````Best Roots  : 5
Worst Roots : 1 3 4``````
Sometimes it happens that we get accepted for partial solutions. It is because judge's input are weak and may not contain all critical input.
forthright48's solution at uDebug for problem 11428 was changed because it wasn't giving correct answers for some critical input, though it was accepted by judge.
It was changed to brianfry713's solution.
Last edited by lighted on Wed Sep 10, 2014 2:33 pm, edited 1 time in total.
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

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

### Re: 10459 - The Tree Root

I uploaded my code and some small random input to:
http://www.udebug.com/UVa/10459
Farsan, your code fails some of those random input cases.

The judge's input only contains trees. lighted's input in the previous post is also invalid.
Check input and AC output for thousands of problems on uDebug!

lighted
Guru
Posts: 585
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

### Re: 10459 - The Tree Root

Invalid input

Code: Select all

``````8
1 5
1 8
1 5
1 5
3 3 4 1 <- node 6 is missing here
2 8 5
1 8
3 7 6 2
``````
I edited input in my previous post. Outputs are still the same
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

Farsan
New poster
Posts: 34
Joined: Fri Aug 12, 2011 6:37 am

### Re: 10459 - The Tree Root

Thanks brianfry713,you always help .Struggled to find out worse roots but at last ACED.

ebb
New poster
Posts: 7
Joined: Sat Nov 19, 2016 8:44 pm

### Re: 10459 - The Tree Root

Hi everyone,

I'm having trouble with this problem. My code (Java) passes all the inputs in this thread and in uDebug, but gets Runtime Error in the judge. I'm pretty sure it is the code that reads the input, because when I wrap it in a try catch I get Wrong Answer. When I remove the actual algorithm instead, I keep getting RE. When catching the exception, it doesn't matter if I stop completely, simply go to the next test case or ignore the exception: I always get Wrong Answer.

Here's my code in case someone can give me a hint of what could be wrong. I've removed the algorithm so we can focus on the input-reading code.

Edit: I removed the code, as I found my mistake.