//#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 vis[100001];
llo vis2[300001];
set<llo> adj2[300001];
llo match[300001];
llo dfs4(llo no){
if(vis2[no]){
return 0;
}
vis2[no]=1;
for(auto k:adj2[no]){
if(match[k]==-1 or dfs4(match[k])){
match[k]=no;
return 1;
}
}
return 0;
}
void dfs3(llo no,llo par=-1){
par2[no]=par;
for(auto j:adj[no]){
if(j!=par){
dfs3(j,no);
}
}
}
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];
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);
/*for(int i=0;i<n;i++){
cout<<par2[i]<<"::";
}
cout<<endl;*/
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);
/* 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(vis[i]==1){
continue;
}
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;
ans++;
}
}
/* for(int i=0;i<=2*n;i++){
match[i]=-1;
}
for(int i=1;i<n;i++){
for(int j=0;j<=2*n;j++){
vis[j]=0;
}
dfs4(i);
}
map<int,int> ans2;
for(int i=0;i<=2*n;i++){
if(match[i]!=-1){
ans2[match[i]]=zz[i];
}
cout<<i<<":"<<match[i]<<endl;
}
for(int i=1;i<n;i++){
cout<<ans2[i]<<":";
if(adj2[i].size()){
cout<<i+1<<" "<<par2[i]+1<<" "<<ans2[i]<<endl;
}
}
cout<<endl;
return 0;*/
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});
}
}
}
/* for(int i=1;i<n;i++){
cout<<ll[i]<<":"<<rr[i]<<endl;
}*/
//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});
adj2[nn].erase(no.b);
adj2[no.b].erase(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});
}*/
ans++;
cout<<nn+1<<" "<<par2[nn]+1<<" "<<zz[no.b]<<endl;
continue;
}
}
break;
}
int ccd=0;
for(auto j:cot2){
if(j.a==1){
ccd++;
}
}
if(ccd>1){
while(true){
continue;
}
}
while(true){
if(cot.size()==0 and cot2.size()==0){
break;
}
ans++;
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});
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]--;
/*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;
}
}
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});
adj2[nn].erase(no.b);
adj2[no.b].erase(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;
}
}
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});
adj2[nn].erase(no.b);
adj2[no.b].erase(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){
cot.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;
continue;
}
/* if(ans!=n-1){
while(true){
continue;
}
}
*/
return 0;
}
Compilation message
minmaxtree.cpp: In function 'int main()':
minmaxtree.cpp:165:13: warning: unused variable 'cc' [-Wunused-variable]
165 | llo aa,bb,cc;
| ^~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
19 ms |
26220 KB |
Expected EOF |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
492 ms |
68852 KB |
Unexpected end of file - int32 expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
291 ms |
93932 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
19 ms |
26220 KB |
Expected EOF |
| 2 |
Halted |
0 ms |
0 KB |
- |
