#include <stdio.h>
#include <vector>
#include <algorithm>
#define pii pair<int,int>
#define ff first
#define ss second
#define ele (1<<18)
#define INF 2e9
using namespace std;
struct node{
int root=INF;
}sgt[ele<<1];
vector<int> edge[222222];
int num_pos=1;
int par[222222];
pii sub[222222];
bool is_gone[222222];
void dfs_num(int v){
sub[v].ff=num_pos;
for(int i=0;i<edge[v].size();i++){
if(is_gone[edge[v][i]]) continue;
is_gone[edge[v][i]]=1;
dfs_num(edge[v][i]);
}
sub[v].ss=num_pos++;
}
void spread_(int w,int l,int r){
int m=(l+r)>>1;
sgt[w<<1].root=min(sgt[w<<1].root,sgt[w].root);
sgt[w<<1|1].root=min(sgt[w<<1|1].root,sgt[w].root);
}
void insert_(int w,int l,int r,int s,int e,int g){
if(s>e) return;
if(sgt[w].root<g) return;
spread_(w,l,r);
if(s==l && e==r){
sgt[w].root=min(sgt[w].root,g);
return;
}
int m=(l+r)>>1;
if(s<=m && sgt[w<<1].root>g) insert_(w<<1,l,m,s,min(m,e),g);
if(m<e && sgt[w<<1|1].root>g) insert_(w<<1|1,m+1,r,max(s,m+1),e,g);
}
int search_(int w,int l,int r,int p){
if(l==p && r==p) return sgt[w].root;
spread_(w,l,r);
int m=(l+r)>>1;
if(p<=m) return search_(w<<1,l,m,p);
return search_(w<<1|1,m+1,r,p);
}
int main(){
int n,q;
scanf("%d %d",&n,&q);
for(int i=2;i<=n;i++){
scanf("%d",&par[i]);
edge[par[i]].push_back(i);
edge[i].push_back(par[i]);
}
is_gone[1]=1; dfs_num(1);
insert_(1,1,ele,1,n,n);
// for(int i=1;i<=n;i++) printf("%d ",sub[i].ff); printf("\n");
// for(int i=1;i<=n;i++) printf("%d ",sub[i].ss); printf("\n\n");
for(int i=1;i<=q;i++){
int a,b,c;
scanf("%d %d %d",&a,&b,&c);
int root_a=search_(1,1,ele,sub[a].ss);
int root_b=search_(1,1,ele,sub[b].ss);
// printf("%d %d\n",root_a,root_b);
if(c){
if(root_a==root_b){
insert_(1,1,ele,sub[a].ff,sub[a].ss,sub[a].ss);
printf("YES\n");
}
else{
insert_(1,1,ele,sub[b].ff,sub[b].ss,sub[b].ss);
printf("NO\n");
}
}
else{
if(root_a==root_b) printf("YES\n");
else printf("NO\n");
}
}
return 0;
}
Compilation message
tree.cpp: In function 'void dfs_num(int)':
tree.cpp:24:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<edge[v].size();i++){
~^~~~~~~~~~~~~~~
tree.cpp: In function 'void spread_(int, int, int)':
tree.cpp:33:9: warning: unused variable 'm' [-Wunused-variable]
int m=(l+r)>>1;
^
tree.cpp: In function 'int main()':
tree.cpp:67:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&n,&q);
~~~~~^~~~~~~~~~~~~~~
tree.cpp:69:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&par[i]);
~~~~~^~~~~~~~~~~~~~
tree.cpp:82:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d",&a,&b,&c);
~~~~~^~~~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
22 ms |
13176 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
22 ms |
13176 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
22 ms |
13176 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
22 ms |
13176 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
22 ms |
13176 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
