//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define ll long long
#define F first
#define S second
#define ull unsigned long long
#define db double
#define ldb long double
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define yes cout<<"YES\n"
#define no cout<<"NO\n"
#define ordered_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>
#define all(x) x.begin(), x.end()
const int mod = 1e9 + 7;
const int N = 500001;
using namespace std;
using namespace __gnu_pbds;
ll n, a, b, c, up[N][22], d[N], m, bg[N], h[N];
map <pair <ll, ll>, ll> ax, an, mx, mn;
map <ll, ll> cx, cn, used;
vector <pair <ll, pair <ll, ll>>> k, mxx, mnn;
vector <ll> g[N];
void dfs (ll v, ll pr){
up[v][0] = pr;
for (int i = 1; i <= 21; i++){
up[v][i] = up[up[v][i - 1]][i - 1];
}
for (int i = 0; i < g[v].size(); i++){
if (g[v][i] != pr){
ax[{v, g[v][i]}] = ax[{g[v][i], v}] = an[{g[v][i], v}] = an[{v, g[v][i]}] = -1;
d[g[v][i]] = d[v] + 1;
dfs (g[v][i], v);
}
}
}
ll lca (ll a, ll b){
if (d[a] < d[b]){
swap (a, b);
}
ll c = abs (d[a] - d[b]);
for (int i = 21; i >= 0; i--){
if ((c >> i) & 1){
a = up[a][i];
}
}
if (a == b){
return a;
}
for (int i = 21; i >= 0; i--){
if (up[a][i] != up[b][i]){
a = up[a][i];
b = up[b][i];
}
}
return up[a][0];
}
void cnt (ll v, ll pr){
for (auto i: g[v]){
if (i != pr){
cx[mx[{i, v}]]++;
cn[mn[{i, v}]]++;
cnt (i, v);
}
}
}
void ans (ll v, ll pr){
for (auto i: g[v]){
if (i != pr){
if (ax[{i, v}] != -1 && used[ax[{i, v}]] == 0){
if (used[{an[{i, v}]}] == 1 || an[{i, v}] == -1){
cn[an[{i, v}]]--;
cx[ax[{i, v}]]--;
used[ax[{i, v}]] = 1;
k.pb({i, {v, ax[{i, v}]}});
}
else{
if (cx[ax[{i, v}]] < cn[mn[{i, v}]]){
cn[an[{i, v}]]--;
cx[ax[{i, v}]]--;
used[ax[{i, v}]] = 1;
k.pb({i, {v, ax[{i, v}]}});
}
else{
cn[mn[{i, v}]]--;
cx[mx[{i, v}]]--;
used[an[{i, v}]] = 1;
k.pb({i, {v, an[{i, v}]}});
}
}
}
else{
if (an[{i, v}] == -1){
k.pb({i, {v, 0}});
cx[ax[{i, v}]]--;
}
else{
k.pb({i, {v, an[{i, v}]}});
used[an[{i, v}]] = 1;
cx[ax[{i, v}]]--;
cn[an[{i, v}]]--;
}
}
ans (i, v);
}
}
}
signed main (){
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n;
for (int i = 1; i < n; i++){
cin >> a >> b;
g[a].pb(b);
g[b].pb(a);
}
d[1] = 1;
dfs (1, 1);
cin >> m;
for (int i = 1; i <= m; i++){
char ch;
cin >> ch >> a >> b >> c;
if (ch == 'M'){
mxx.pb ({c, {a, b}});
}
else{
mnn.pb ({c, {a, b}});
}
}
sort (all (mxx));
sort (all (mnn));
reverse (all (mxx));
for (auto i: mxx){
ll lc = lca (i.S.F, i.S.S);
a = i.S.F, b = i.S.S;
while (a != lc){
ax[{a, up[a][0]}] = ax[{up[a][0], a}] = i.F;
a = up[a][0];
}
while (b != lc){
ax[{b, up[b][0]}] = ax[{up[b][0], b}] = i.F;
b = up[b][0];
}
}
for (auto i: mnn){
ll lc = lca (i.S.F, i.S.S);
a = i.S.F, b = i.S.S;
while (a != lc){
an[{a, up[a][0]}] = an[{up[a][0], a}] = i.F;
a = up[a][0];
}
while (b != lc){
an[{b, up[b][0]}] = an[{up[b][0], b}] = i.F;
b = up[b][0];
}
}
cnt (1, 1);
ans (1, 1);
for (auto i: k){
cout << i.F << ' ' << i.S.F << ' ' << i.S.S << '\n';
}
}
Compilation message
minmaxtree.cpp: In function 'void dfs(long long int, long long int)':
minmaxtree.cpp:37:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
37 | for (int i = 0; i < g[v].size(); i++){
| ~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
12112 KB |
Output is correct |
| 2 |
Incorrect |
8 ms |
12124 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1063 ms |
76768 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
432 ms |
60624 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
12112 KB |
Output is correct |
| 2 |
Incorrect |
8 ms |
12124 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
