//#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first
#define b second
#define endl '\n'
llo n,k;
vector<llo> pre[100001];
set<llo> cur[100001];
vector<llo> adj[100001];
vector<llo> pre2[100001];
llo ll[100001];
llo rr[100001];
llo par2[100001];
llo dfs(llo no,llo par=-1){
llo ma=-1;
llo ind=-1;
par2[no]=par;
vector<llo> ss;
for(auto j:adj[no]){
if(j!=par){
llo x=dfs(j,no);
ss.pb(x);
//cout<<no<<":"<<j<<":"<<x<<endl;
if((llo)cur[x].size()>ma){
ma=cur[x].size();
ind=x;
}
}
}
if(ma==-1){
//cout<<no<<":"<<endl;
ind=no;
}
for(auto j:ss){
if(j!=ind){
for(auto j:cur[j]){
if(cur[ind].find(j)!=cur[ind].end()){
cur[ind].erase(j);
continue;
}
cur[ind].insert(j);
}
cur[j].clear();
}
}
for(auto j:pre[no]){
if(cur[ind].find(j)!=cur[ind].end()){
cur[ind].erase(j);
continue;
}
cur[ind].insert(j);
}
if(par!=-1){
//cout<<no+1<<" "<<par+1<<" ";
if(cur[ind].size()){
rr[no]=(*(cur[ind].begin()));
// cout<<(*(cur[ind].begin()))<<endl;
}//
else{
rr[no]=-1;
// cout<<1<<endl;
}
}
return ind;
}
llo dfs2(llo no,llo par=-1){
llo ma=-1;
llo ind=-1;
vector<llo> ss;
for(auto j:adj[no]){
if(j!=par){
llo x=dfs2(j,no);
ss.pb(x);
//cout<<no<<":"<<j<<":"<<x<<endl;
if((llo)cur[x].size()>ma){
ma=cur[x].size();
ind=x;
}
}
}
if(ma==-1){
//cout<<no<<":"<<endl;
ind=no;
}
for(auto j:ss){
if(j!=ind){
for(auto j:cur[j]){
if(cur[ind].find(j)!=cur[ind].end()){
cur[ind].erase(j);
continue;
}
cur[ind].insert(j);
}
cur[j].clear();
}
}
for(auto j:pre2[no]){
if(cur[ind].find(-j)!=cur[ind].end()){
cur[ind].erase(-j);
continue;
}
cur[ind].insert(-j);
}
if(par!=-1){
//cout<<no+1<<" "<<par+1<<" ";
if(cur[ind].size()){
ll[no]=-(*(cur[ind].begin()));
// cout<<(*(cur[ind].begin()))<<endl;
}//
else{
ll[no]=-1;
// cout<<1<<endl;
}
}
return ind;
}
set<llo> adj2[300001];
llo co[300001];
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin>>n;
for(llo i=0;i<n-1;i++){
llo aa,bb,cc;
cin>>aa>>bb;
aa--;
bb--;
adj[aa].pb(bb);
adj[bb].pb(aa);
}
cin>>k;
set<llo> xx;
for(llo i=0;i<k;i++){
char s;
cin>>s;
llo aa,bb,cc;
cin>>aa>>bb>>cc;
aa--;
bb--;
xx.insert(cc);
if(s=='M'){
pre[aa].pb(cc);
pre[bb].pb(cc);
}
else{
pre2[aa].pb(cc);
pre2[bb].pb(cc);
}
}
dfs(0);
for(llo i=0;i<n;i++){
cur[i].clear();
}
dfs2(0);
/* for(llo i=1;i<n;i++){
cout<<ll[i]<<":"<<rr[i]<<endl;
}*/
llo ind=n;
map<llo,llo> yy;
map<llo,llo> zz;
for(auto i:xx){
yy[i]=ind;
zz[ind]=i;
ind++;
}
for(llo i=1;i<n;i++){
if(ll[i]!=-1){
adj2[i].insert(yy[ll[i]]);
adj2[yy[ll[i]]].insert(i);
//cout<<i<<":"<<ll[i]<<endl;
}
if(rr[i]!=-1){
adj2[i].insert(yy[rr[i]]);
adj2[yy[rr[i]]].insert(i);
// cout<<i<<":"<<rr[i]<<endl;
}
if(ll[i]==-1 and rr[i]==-1){
cout<<i+1<<" "<<par2[i]+1<<" "<<1<<endl;
}
}
set<pair<llo,llo>> cot;
set<pair<llo,llo>> cot2;
for(llo i=1;i<=200000;i++){
if(adj2[i].size()>0){
co[i]=adj2[i].size();
if(i<n){
cot.insert({adj2[i].size(),i});
}
else{
cot2.insert({adj2[i].size(),i});
}
}
}
//return 0;
/*for(auto j:cot2){
cout<<zz[j.b]<<",,"<<j.a<<endl;
}
for(auto j:cot){
cout<<j.b<<",,,"<<j.a<<endl;
}*/
while(true){
if(cot.size()==0 and cot2.size()==0){
break;
}
if(cot2.size()>0){
pair<llo,llo> no=*(cot2.begin());
if(no.a==1){
llo nn=*(adj2[no.b].begin());
cot2.erase({no});
co[no.b]--;
cot.erase({co[nn],nn});
for(auto j:adj2[nn]){
cot2.erase({co[j],j});
adj2[j].erase(nn);
co[j]--;
if(co[j]>0){
cot2.insert({co[j],j});
}
}
co[nn]--;
/*if(co[nn]>0){
cot.insert({co[nn],nn});
}*/
cout<<nn+1<<" "<<par2[nn]+1<<" "<<zz[no.b]<<endl;
/* for(auto j:cot2){
cout<<zz[j.b]<<",,"<<j.a<<endl;
}
for(auto j:cot){
cout<<j.b<<",,,"<<j.a<<endl;
}*/
continue;
}
}
if(cot.size()>0){
pair<llo,llo> no=*(cot.begin());
if(no.a==1){
llo nn=*(adj2[no.b].begin());
cot.erase({no});
co[no.b]--;
cot2.erase({co[nn],nn});
for(auto j:adj2[nn]){
cot.erase({co[j],j});
adj2[j].erase(nn);
co[j]--;
if(co[j]>0){
cot2.insert({co[j],j});
}
}
co[nn]--;
/*if(co[nn]>0){
cot2.insert({co[nn],nn});
}*/
cout<<no.b+1<<" "<<par2[no.b]+1<<" "<<zz[nn]<<endl;
/*for(auto j:cot2){
cout<<zz[j.b]<<",,"<<j.a<<endl;
}
for(auto j:cot){
cout<<j.b<<",,,"<<j.a<<endl;
}
*/
continue;
}
}
pair<llo,llo> no=*(cot2.begin());
llo nn=*(adj2[no.b].begin());
cot2.erase({no});
co[no.b]--;
cot.insert({co[no.b],no.b});
cot.erase({co[nn],nn});
for(auto j:adj2[nn]){
cot2.erase({co[j],j});
adj2[j].erase(nn);
co[j]--;
if(co[j]>0){
cot2.insert({co[j],j});
}
}
for(auto j:adj2[no.b]){
cot.erase({co[j],j});
adj2[j].erase(no.b);
co[j]--;
if(co[j]>0){
cot2.insert({co[j],j});
}
}
co[nn]--;
/*if(co[nn]>0){
cot.insert({co[nn],nn});
}*/
cout<<nn+1<<" "<<par2[nn]+1<<" "<<zz[no.b]<<endl;
break;
}
return 0;
}
Compilation message
minmaxtree.cpp: In function 'int main()':
minmaxtree.cpp:140:13: warning: unused variable 'cc' [-Wunused-variable]
140 | llo aa,bb,cc;
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
21 ms |
26220 KB |
Unexpected end of file - int32 expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
512 ms |
69612 KB |
Unexpected end of file - int32 expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
251 ms |
47468 KB |
Integer 77945 violates the range [1, 68552] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
21 ms |
26220 KB |
Unexpected end of file - int32 expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
