//#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[300001];
set<llo> cur[300001];
vector<llo> adj[300001];
vector<llo> pre2[300001];
llo ll[300001];
llo rr[300001];
llo par2[300001];
llo vis[300001];
llo vis2[300001];
set<llo> adj2[300001];
llo match[300001];
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;
}
llo co[300001];
vector<pair<llo,llo>> adj3[300001];
llo vis3[300001];
llo vis4[300001];
pair<llo,llo> mm;
llo mm2;
map<llo,llo> zz;
void dfs3(int no,int par=-1){
vis3[no]=1;
for(auto j:adj3[no]){
if(vis3[j.a]==0){
dfs3(j.a,no);
}
else if(j.a!=par){
mm={j.a,no};
mm2=j.b;
}
}
}
llo vis5[300001];
void dfs4(int no,int par=-1){
vis4[no]=1;
for(auto j:adj3[no]){
/*if(j.a==mm.b and no==mm.a){
continue;
}*/
if(vis4[j.a]==0){
vis5[j.b]=1;
cout<<j.b+1<<" "<<par2[j.b]+1<<" "<<zz[j.a]<<endl;
dfs4(j.a,no);
}
else if(j.a!=par){
}
}
}
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;
//dfs3(0);
llo ans=0;
for(llo i=0;i<k;i++){
char s;
cin>>s;
llo aa,bb,cc;
cin>>aa>>bb>>cc;
aa--;
bb--;
/*if(bb==par2[aa]){
swap(aa,bb);
}
if(aa==par2[bb]){
cout<<aa+1<<" "<<bb+1<<" "<<cc<<endl;
vis[bb]=1;
ans++;
continue;
}*/
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);
llo ind=n;
map<llo,llo> yy;
for(auto i:xx){
yy[i]=ind;
zz[ind]=i;
ind++;
}
for(llo i=1;i<n;i++){
/*if(vis[i]==1){
continue;
}*/
if(ll[i]!=-1){
adj2[i].insert(yy[ll[i]]);
adj2[yy[ll[i]]].insert(i);
}
if(rr[i]!=-1){
adj2[i].insert(yy[rr[i]]);
adj2[yy[rr[i]]].insert(i);
}
if(ll[i]==-1 and rr[i]==-1){
cout<<i+1<<" "<<par2[i]+1<<" "<<1<<endl;
ans++;
}
// cout<<ll[i]<<":"<<rr[i]<<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});
}
}
}
while(true){
if(cot.size()==0){
break;
}
if(cot.size()>0){
pair<llo,llo> no=*(cot.begin());
if(no.a==1){
vis5[no.b]=1;
llo nn=*(adj2[no.b].begin());
cot.erase({no});
co[no.b]--;
cot2.erase({co[nn],nn});
adj2[nn].erase(no.b);
adj2[no.b].erase(nn);
for(auto j:adj2[nn]){
cot.erase({co[j],j});
adj2[j].erase(nn);
co[j]--;
if(co[j]>0){
cot.insert({co[j],j});
}
}
co[nn]--;
cout<<no.b+1<<" "<<par2[no.b]+1<<" "<<zz[nn]<<endl;
continue;
}
}
break;
}
for(auto j:cot){
adj3[yy[ll[j.b]]].pb({yy[rr[j.b]],j.b});
adj3[yy[rr[j.b]]].pb({yy[ll[j.b]],j.b});
//cout<<yy[ll[j.b]]<<","<<yy[rr[j.b]]<<endl;
}
// cout<<(cot.size())<<endl;
for(int i=1;i<=2*n;i++){
if(vis3[i]==0){
if(adj3[i].size()>0){
dfs3(i);
dfs4(mm.a);
// cout<<11<<endl;
cout<<mm2+1<<" "<<par2[mm2]+1<<" "<<zz[mm.a]<<endl;
vis5[mm2]=1;
}
}
}
for(int i=1;i<n;i++){
if(vis5[i]==0){
cout<<i+1<<" "<<par2[i]+1<<" "<<ll[i]<<endl;
}
}
return 0;
}
Compilation message
minmaxtree.cpp: In function 'int main()':
minmaxtree.cpp:180:13: warning: unused variable 'cc' [-Wunused-variable]
180 | llo aa,bb,cc;
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
38 ms |
56812 KB |
Output is correct |
| 2 |
Correct |
38 ms |
56940 KB |
Output is correct |
| 3 |
Correct |
39 ms |
56812 KB |
Output is correct |
| 4 |
Correct |
38 ms |
56812 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
502 ms |
99948 KB |
Expected EOF |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
285 ms |
78828 KB |
Expected EOF |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
38 ms |
56812 KB |
Output is correct |
| 2 |
Correct |
38 ms |
56940 KB |
Output is correct |
| 3 |
Correct |
39 ms |
56812 KB |
Output is correct |
| 4 |
Correct |
38 ms |
56812 KB |
Output is correct |
| 5 |
Incorrect |
502 ms |
99948 KB |
Expected EOF |
| 6 |
Halted |
0 ms |
0 KB |
- |
