#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define st first
#define nd second
#define pp pair<int,int>
const int N = 7e4 + 4;
const int mod = 1e9 + 7;
vector < pp > V[N],A[N],B[N];
vector<pp> M[N];
int H[N],W[N];
int ans[N],U[N],sz[N],T[N],Mn[N],Mx[N],C;
void f(int x, int p, int n){
int h=1; sz[x] = 1;
for(auto y : V[x]){
if(U[y.st] || y.st == p) continue;
f(y.st,x,n);
sz[x] += sz[y.st];
if(sz[y.st] > n/2) h=0;
}
if(h && n-sz[x] <= n/2) C=x;
}
void g(int x, int p, int roo){
T[x] = roo;
for(auto y : V[x]){
if(U[y.st] || y.st == p) continue;
g(y.st,x,roo);
}
}
pp h(int x, int p, int i){
sz[x] = 1;
int mn = 0;
for(auto t : A[x]) if(T[t.st] && T[t.st] != T[x]) mn = max(mn , t.nd);
int mx = mod;
for(auto t : B[x]) if(T[t.st] && T[t.st] != T[x]) mx = min(mx , t.nd);
pp a;
for(auto y : V[x]){
if(U[y.st] || y.st == p) continue;
a = h(y.st,x,y.nd);
mn = max(mn , a.st);
mx = min(mx , a.nd);
sz[x] += sz[y.st];
}
Mn[i] = max(Mn[i] , mn);
Mx[i] = min(Mx[i] , mx);
return mp(mn,mx);
}
void slv(int x, int n){
f(x,-1,n);
x = C;
U[x] = 1;
T[x] = -1;
for(auto y : V[x]){
if(U[y.st]) continue;
g(y.st,x,y.st);
}
h(x,-1,0);
g(x,-1,0);
for(auto y : V[x]) if(!U[y.st]) slv(y.st,sz[y.st]);
}
void ff(int x){
H[x] = 1;
for(auto y : M[x]){
if(H[y.st]) continue;
ans[y.nd] = y.st;
ff(y.st);
}
}
void gg(int x, int p){
H[x] = 1;
for(auto y : M[x]){
if(y.nd == p) continue;
if(!H[y.st]) { ans[y.nd] = x; gg(y.st,y.nd); }
else if(!ans[y.nd]) ans[y.nd] = x;
}
}
int n,k,i,x,y,z,uu[N],vv[N],K[N];
char c;
int main(){
scanf("%d",&n);
for(i=1;i<n;i++){
scanf("%d%d",&x,&y);
V[x].pb(mp(y,i));
V[y].pb(mp(x,i));
Mx[i] = mod;
uu[i] = x; vv[i] = y;
}
scanf("%d",&k);
for(i=1;i<=k;i++){
scanf(" %c%d%d%d",&c,&x,&y,&z);
K[i] = z;
if(c == 'm') { A[x].pb(mp(y,z)); A[y].pb(mp(x,z)); }
else { B[x].pb(mp(y,z)); B[y].pb(mp(x,z)); }
}
slv(1,n);
K[++k] = 0;
K[++k] = mod;
sort(K+1 , K+k+1);
for(i=1;i<n;i++)
if(Mn[i] != 0 || Mx[i] != mod){
x = lower_bound(K+1 , K+k+1 , Mn[i]) - K;
y = lower_bound(K+1 , K+k+1 , Mx[i]) - K;
M[x].pb(mp(y,i));
M[y].pb(mp(x,i));
W[x]++; W[y]++;
}
ff(1); ff(k);
for(i=1;i<=k;i++){
x = i;
if(H[x]) continue;
for(; W[x] == 1 ; x = z) {
W[x]--;
H[x] = 1;
z = 0;
for(auto y : M[x]){
W[y.st]--;
if(W[y.st] > 0){
ans[y.nd] = x;
z = y.st;
}
}
}
}
for(i=1;i<=k;i++)
if(!H[i])
gg(i,0);
for(i=1;i<n;i++)
printf("%d %d %d\n", uu[i], vv[i], ans[i] ? E[ ans[i] ] : Mx[i]);
return 0;
}
Compilation message
minmaxtree.cpp: In function 'int main()':
minmaxtree.cpp:136:53: error: 'E' was not declared in this scope
printf("%d %d %d\n", uu[i], vv[i], ans[i] ? E[ ans[i] ] : Mx[i]);
^
minmaxtree.cpp:85:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
~~~~~^~~~~~~~~
minmaxtree.cpp:87:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&x,&y);
~~~~~^~~~~~~~~~~~~~
minmaxtree.cpp:93:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&k);
~~~~~^~~~~~~~~
minmaxtree.cpp:95:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf(" %c%d%d%d",&c,&x,&y,&z);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
