/*
author : SilentVisitor
created on 12.01.22 12.52 A.M.
*/
#include<bits/stdc++.h>
using namespace std;
#ifdef _DEBUG
#include "algo/debug.h"
#else
#define debug(...) 69420
#endif
#define deb(...) union
#define ll long long
#define i64 int64_t
#define ff first
#define ss second
#define all(c) c.begin(), c.end()
#define rall(c) c.rbegin(), c.rend()
#define sz(s) s.size()
vector<char> data = {'a', 'e', 'i', 'o', 'u'};
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
template<class T> bool ckmin(T& a, const T& b) { return a > b ? a = b, 1 : 0; }
const int N = 10101;
char C[N];
vector<int> vec,g[N],vmn[N],vmx[N];
vector<pair<int,pair<int,int>>> G[N];
set<int> smn[N],smx[N];
int n, m, rt, a[N], W[N], U[N], V[N], vis[N];
map<pair<int, int>, int> mark;
void solve(){
cin >> n;
for(int i = 1; i < n; i += 1){
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
cin >> m;
for(int i = 0; i < m; i += 1){
cin >> C[i] >> U[i] >> V[i] >> W[i];
vec.push_back(W[i]);
}
sort(all(vec));
for(int i = 0; i < m; i += 1){
W[i] = lower_bound(all(vec), W[i]) - vec.begin()+1;
int u = U[i], v = V[i], w = W[i];
if(C[i] == 'M'){
vmx[u].push_back(w);
vmx[v].push_back(w);
}
else {
vmn[u].push_back(w);
vmn[v].push_back(w);
}
}
function<void(int, int, int, int)> out = [&](int s, int t, int u, int v) {
int res = 0;
cout<<s<<" "<<t<<" ";
if(u==0 || v==0) res=max(u,v);
else res=v;
res = max(res, 1);
cout<<vec[res-1];
cout<<endl;
};
function<void(int, int)> dfs = [&](int u, int p){
int x=0;
for(auto v : g[u]){
if(v==p) continue ;
dfs(v,u);
if(smn[v].size()+smx[v].size()>smn[x].size()+smx[x].size()){
x=v;
}
}
swap(smn[u],smn[x]);
swap(smx[u],smx[x]);
for(auto x : vmn[u]){
if(smn[u].find(x)!=smn[u].end()) smn[u].erase(x);
else smn[u].insert(x);
}
for(auto x : vmx[u]){
if(smx[u].find(x)!=smx[u].end()) smx[u].erase(x);
else smx[u].insert(x);
}
for(auto v : g[u]){
if(v==p || v==x) continue ;
for(auto x : smn[v]){
if(smn[u].find(x)!=smn[u].end()) smn[u].erase(x);
else smn[u].insert(x);
}
for(auto x : smx[v]){
if(smx[u].find(x)!=smx[u].end()) smx[u].erase(x);
else smx[u].insert(x);
}
}
if(u==1) return ;
int l=0,r=0;
if(smn[u].size()) l=*smn[u].rbegin();
if(smx[u].size()) r=*smx[u].begin();
G[l].push_back({r,{u,p}});
G[r].push_back({l,{u,p}});
};
function<void(int, int)> dfs1 = [&](int u, int p){
vis[u] = 1;
for(auto v : G[u]){
if(vis[v.ff]){
if(p!=v.ff) rt=v.ff;
continue;
}
dfs1(v.ff,u);
}
};
function<void(int)> dfs2 = [&](int u) {
vis[u] = 2;
for(auto p : G[u]){
int v = p.ff, s = p.ss.ff, t = p.ss.ss;
if(!mark[make_pair(s, t)]){
mark[make_pair(s, t)] = 1;
out(s, t, u, v);
}
if(vis[v] < 2)
dfs2(v);
}
};
function<void(int)> exact = [&](int node) {
rt = 0;
dfs1(node, node);
dfs2(rt);
};
dfs(1, 1);
for(int i = 0; i < m+1; i += 1){
if(!vis[i])
exact(i);
}
}
main(void){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
solve();
return 0;
}
Compilation message
minmaxtree.cpp:140:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
140 | main(void){
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2264 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2240 KB |
Output is correct |
| 3 |
Correct |
2 ms |
2132 KB |
Output is correct |
| 4 |
Correct |
1 ms |
2132 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
4308 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
4 ms |
4296 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2264 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2240 KB |
Output is correct |
| 3 |
Correct |
2 ms |
2132 KB |
Output is correct |
| 4 |
Correct |
1 ms |
2132 KB |
Output is correct |
| 5 |
Runtime error |
3 ms |
4308 KB |
Execution killed with signal 11 |
| 6 |
Halted |
0 ms |
0 KB |
- |
