I need a code in c !!! ASAP !!!!! John has got a tree with N vertices. The verti

Question

I need a code in c !!! ASAP !!!!!
John has got a tree with N vertices. The vertices are numbered from 1 to N. He considers vertex 1 as the root of the tree. Each vertex of the tree contains a character C.
Now John is doing a weird experiment with this tree.
He often changes the character of a node in the tree and then sometimes he randomly selects a node v and tries to form a palindrome with all the characters in the subtree of node v.
But since John is very busy man and has a lot of other important experiments to do he needs your help on this one.
INPUT:
First line of the input contains an integer N (1<=N<=100000) denoting the number of vertices.
Next N-1 lines contains two integers A and B (1<=A, B<=N) which means there is an edge between vertex A and B.
Next line contains a string of length N. The ith character of this string denotes the character in node i.
Then there will be an integer M (1<=M<=100000) in a separate line denoting the number of queries. Next M lines will contain a query.
Each query will be in one of the following form:
0 x C: which means the character of node x has been changed to C.
1 x: which means you are asked to answer if a palindrome can be formed with all the characters in the sub tree of node x. There will be at least one query of this type.
OUTPUT:
For each query of the form “1 x” print “YES” if a palindrome can be formed with all the characters in subtree of node x. Otherwise print “NO” (without the quotes).
(All the characters in the input will be small letters of English alphabet. i.e. a, b, c… x, y, z). I need a code in c !!! ASAP !!!!!
John has got a tree with N vertices. The vertices are numbered from 1 to N. He considers vertex 1 as the root of the tree. Each vertex of the tree contains a character C.
Now John is doing a weird experiment with this tree.
He often changes the character of a node in the tree and then sometimes he randomly selects a node v and tries to form a palindrome with all the characters in the subtree of node v.
But since John is very busy man and has a lot of other important experiments to do he needs your help on this one.
INPUT:
First line of the input contains an integer N (1<=N<=100000) denoting the number of vertices.
Next N-1 lines contains two integers A and B (1<=A, B<=N) which means there is an edge between vertex A and B.
Next line contains a string of length N. The ith character of this string denotes the character in node i.
Then there will be an integer M (1<=M<=100000) in a separate line denoting the number of queries. Next M lines will contain a query.
Each query will be in one of the following form:
0 x C: which means the character of node x has been changed to C.
1 x: which means you are asked to answer if a palindrome can be formed with all the characters in the sub tree of node x. There will be at least one query of this type.
OUTPUT:
For each query of the form “1 x” print “YES” if a palindrome can be formed with all the characters in subtree of node x. Otherwise print “NO” (without the quotes).
(All the characters in the input will be small letters of English alphabet. i.e. a, b, c… x, y, z).
John has got a tree with N vertices. The vertices are numbered from 1 to N. He considers vertex 1 as the root of the tree. Each vertex of the tree contains a character C.
Now John is doing a weird experiment with this tree.
He often changes the character of a node in the tree and then sometimes he randomly selects a node v and tries to form a palindrome with all the characters in the subtree of node v.
But since John is very busy man and has a lot of other important experiments to do he needs your help on this one.
INPUT:
First line of the input contains an integer N (1<=N<=100000) denoting the number of vertices.
Next N-1 lines contains two integers A and B (1<=A, B<=N) which means there is an edge between vertex A and B.
Next line contains a string of length N. The ith character of this string denotes the character in node i.
Then there will be an integer M (1<=M<=100000) in a separate line denoting the number of queries. Next M lines will contain a query.
Each query will be in one of the following form:
0 x C: which means the character of node x has been changed to C.
1 x: which means you are asked to answer if a palindrome can be formed with all the characters in the sub tree of node x. There will be at least one query of this type.
OUTPUT:
For each query of the form “1 x” print “YES” if a palindrome can be formed with all the characters in subtree of node x. Otherwise print “NO” (without the quotes).
(All the characters in the input will be small letters of English alphabet. i.e. a, b, c… x, y, z). John has got a tree with N vertices. The vertices are numbered from 1 to N. He considers vertex 1 as the root of the tree. Each vertex of the tree contains a character C.
Now John is doing a weird experiment with this tree.
He often changes the character of a node in the tree and then sometimes he randomly selects a node v and tries to form a palindrome with all the characters in the subtree of node v.
But since John is very busy man and has a lot of other important experiments to do he needs your help on this one.
INPUT:
First line of the input contains an integer N (1<=N<=100000) denoting the number of vertices.
Next N-1 lines contains two integers A and B (1<=A, B<=N) which means there is an edge between vertex A and B.
Next line contains a string of length N. The ith character of this string denotes the character in node i.
Then there will be an integer M (1<=M<=100000) in a separate line denoting the number of queries. Next M lines will contain a query.
Each query will be in one of the following form:
0 x C: which means the character of node x has been changed to C.
1 x: which means you are asked to answer if a palindrome can be formed with all the characters in the sub tree of node x. There will be at least one query of this type.
OUTPUT:
For each query of the form “1 x” print “YES” if a palindrome can be formed with all the characters in subtree of node x. Otherwise print “NO” (without the quotes).
(All the characters in the input will be small letters of English alphabet. i.e. a, b, c… x, y, z). John has got a tree with N vertices. The vertices are numbered from 1 to N. He considers vertex 1 as the root of the tree. Each vertex of the tree contains a character C.
Now John is doing a weird experiment with this tree.
He often changes the character of a node in the tree and then sometimes he randomly selects a node v and tries to form a palindrome with all the characters in the subtree of node v.
But since John is very busy man and has a lot of other important experiments to do he needs your help on this one.
INPUT:
First line of the input contains an integer N (1<=N<=100000) denoting the number of vertices.
Next N-1 lines contains two integers A and B (1<=A, B<=N) which means there is an edge between vertex A and B.
Next line contains a string of length N. The ith character of this string denotes the character in node i.
Then there will be an integer M (1<=M<=100000) in a separate line denoting the number of queries. Next M lines will contain a query.
Each query will be in one of the following form:
0 x C: which means the character of node x has been changed to C.
1 x: which means you are asked to answer if a palindrome can be formed with all the characters in the sub tree of node x. There will be at least one query of this type.
OUTPUT:
For each query of the form “1 x” print “YES” if a palindrome can be formed with all the characters in subtree of node x. Otherwise print “NO” (without the quotes).
(All the characters in the input will be small letters of English alphabet. i.e. a, b, c… x, y, z).

Explanation / Answer

#include<stdio.h>

#include<stdlib.h>

#include<stdbool.h>

typedef struct Treenode{

char val;

int child;

int* childs;

}treenode;

treenode* tree;

void add_child(int a,int b){

if(tree[a-1].child==0){

tree[a-1].childs = malloc(sizeof(int));

tree[a-1].childs[tree[a-1].child]=b-1;

tree[a-1].child+=1;

}

else{

tree[a-1].childs = realloc(tree[a-1].childs,sizeof(int));

tree[a-1].childs[tree[a-1].child]=b-1;

tree[a-1].child+=1;

}

}

void update_count(int* a,int x){

if(tree[x].child==0){

a[(int)tree[x].val]+=1;

return;

}

else{

int i;

for(i=0;i<tree[x].child;i++){

update_count(a,tree[x].childs[i]);

}

}

}

bool is_palindrome(int x){

int* a=malloc(256*sizeof(int));

for(int i=0;i<256;i++){

a[i]=0;

}

update_count(a,x);

int sum=0;

for(int i=0;i<256;i++){

a[i]%=2;

sum+=a[i];

}

return (sum<2);

}

int main(){

int N,a,b;

scanf("%d",&N);

tree = malloc(N*sizeof(treenode));

for(int i=0;i<N;i++){

tree[i].child=0;

tree[i].childs=NULL;

}

for(int i=0;i<N-1;i++){

scanf("%d %d",&a,&b);

add_child(a,b);

}

char s[N];

scanf("%s",s);

int M;

scanf("%d",&M);

char c;

while(M--){

scanf("%d",&a);

switch(a){

case 0:{

scanf("%d %c",&b,&c);

s[b-1]=c;

break;

}

case 1:{

scanf("%d",&b);

if(is_palindrome(b-1))

printf("YES");

else

printf("NO");

break;

}

}

}

return 0;

}

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.