#include <bits/stdc++.h>
using namespace std;
typedef int ll;
typedef unsigned long long ull;
const ll INF = 1e9+7;
const ll MOD = 998244353;
typedef pair<ll,ll> ii;
#define iii pair<ii,ll>
#define f(i,a,b) for(ll i = a;i < b;i++)
#define pb push_back
#define vll vector<ll>
#define F first
#define S second
#define all(x) (x).begin(), (x).end()
///I hope I will get uprating and don't make mistakes
///I will never stop programming
///sqrt(-1) Love C++
///Please don't hack me
///@TheofanisOrfanou Theo830
///Think different approaches (bs,dp,greedy,graphs,shortest paths,mst)
///Stay Calm
///Look for special cases
///Beware of overflow and array bounds
///Think the problem backwards
///Training
vector<vll>adj;
ll an[70005][20];
ll par[140005];
ll depth[70005];
vector<ll>exo[70005][2][2];
ll timi[70005][2];
set<ll>cur[140005];
ll find_par(ll a){
if(par[a] == a){
return a;
}
return par[a] = find_par(par[a]);
}
void enose(ll a,ll b){
ll p1 = find_par(a);
ll p2 = find_par(b);
if(cur[p1].size() < cur[p2].size()){
swap(p1,p2);
}
par[p1] = p2;
for(auto x:cur[p1]){
cur[p2].insert(x);
}
cur[p1] = set<ll>();
}
void build(ll idx,ll p){
an[idx][0] = p;
f(j,1,20){
an[idx][j] = an[an[idx][j-1]][j-1];
}
for(auto x:adj[idx]){
if(x != p){
depth[x] = 1 + depth[idx];
build(x,idx);
}
}
}
ll kth(ll a,ll k){
ll pos = 0;
while(k){
if(k % 2){
a = an[a][pos];
}
k /= 2;
pos++;
}
return a;
}
void lca(ll a,ll b,bool m,ll c){
if(depth[a] > depth[b]){
swap(a,b);
}
ll A = a,B = b;
b = kth(b,depth[b] - depth[a]);
if(a == b){
exo[a][m][1].pb(c);
exo[B][m][0].pb(c);
return;
}
for(ll j = 19;j >= 0;j--){
if(an[a][j] != an[b][j]){
a = an[a][j];
b = an[b][j];
}
}
exo[an[a][0]][m][1].pb(c);
exo[B][m][0].pb(c);
exo[A][m][0].pb(c);
}
void solve(ll idx,ll p){
cur[idx*2].insert(0);
cur[idx*2+1].insert(1e9+7);
par[idx*2] = idx*2;
par[idx*2+1] = idx*2+1;
for(auto x:adj[idx]){
if(x != p){
solve(x,idx);
enose(x*2,idx*2);
enose(x*2+1,idx*2+1);
}
}
f(j,0,2){
for(auto x:exo[idx][j][0]){
cur[find_par(idx*2+j)].insert(x);
}
}
f(j,0,2){
for(auto x:exo[idx][j][1]){
cur[find_par(idx*2+j)].erase(x);
}
}
timi[idx][0] = (*cur[find_par(idx*2)].rbegin());
timi[idx][1] = (*cur[find_par(idx*2+1)].begin());
}
int main(void){
ios_base::sync_with_stdio(0);
cin.tie(0);
ll n;
cin>>n;
adj.assign(n+5,vll());
f(i,0,n-1){
ll a,b;
cin>>a>>b;
adj[a].pb(b);
adj[b].pb(a);
}
build(1,0);
ll q;
cin>>q;
while(q--){
char c;
ll x,y,z;
cin>>c>>x>>y>>z;
lca(x,y,c == 'M',z);
}
solve(1,0);
bool ek[n+5] = {0};
ll posa[n+5];
map<ll,ll>mp;
map<ll,vll>adj;
set<ii>ex;
f(i,2,n+1){
adj[timi[i][0]].pb(i);
adj[timi[i][1]].pb(i);
mp[timi[i][0]]++;
mp[timi[i][1]]++;
}
for(auto x:mp){
if(x.F != 0 && x.F != 1e9+7){
ex.insert(ii(x.S,x.F));
}
}
while(!ex.empty()){
auto it = ex.begin();
ii f = (*it);
if(f.F == 0){
assert(0);
break;
}
ex.erase(f);
while(ek[adj[f.S].back()]){
adj[f.S].pop_back();
}
ek[adj[f.S].back()] = 1;
posa[adj[f.S].back()] = f.S;
ll c = 0;
if(timi[adj[f.S].back()][0] == f.S){
c ^= 1;
}
auto it2 = ex.lower_bound(ii(mp[timi[adj[f.S].back()][c]],timi[adj[f.S].back()][c]));
if(it2 != ex.end() && (*it2) == ii(mp[timi[adj[f.S].back()][c]],timi[adj[f.S].back()][c])){
f = (*it2);
ex.erase(f);
mp[timi[adj[f.S].back()][c]]--;
f.F--;
ex.insert(f);
}
}
f(i,2,n+1){
ll val;
if(!ek[i]){
val = timi[i][0];
}
else{
val = posa[i];
}
cout<<i<<" "<<an[i][0]<<" "<<val<<"\n";
}
}
/*
7
1 2
2 5
2 4
1 3
3 6
6 7
3
M 7 2 300
M 4 5 24
M 6 4 22
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
13396 KB |
Output is correct |
| 2 |
Correct |
7 ms |
13396 KB |
Output is correct |
| 3 |
Correct |
7 ms |
13440 KB |
Output is correct |
| 4 |
Correct |
7 ms |
13396 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
397 ms |
49276 KB |
Output is correct |
| 2 |
Correct |
450 ms |
42564 KB |
Output is correct |
| 3 |
Execution timed out |
1076 ms |
35532 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
182 ms |
32600 KB |
Output is correct |
| 2 |
Correct |
186 ms |
32852 KB |
Output is correct |
| 3 |
Correct |
188 ms |
37196 KB |
Output is correct |
| 4 |
Correct |
162 ms |
41716 KB |
Output is correct |
| 5 |
Correct |
190 ms |
34156 KB |
Output is correct |
| 6 |
Correct |
203 ms |
35332 KB |
Output is correct |
| 7 |
Correct |
238 ms |
33736 KB |
Output is correct |
| 8 |
Correct |
301 ms |
33344 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
13396 KB |
Output is correct |
| 2 |
Correct |
7 ms |
13396 KB |
Output is correct |
| 3 |
Correct |
7 ms |
13440 KB |
Output is correct |
| 4 |
Correct |
7 ms |
13396 KB |
Output is correct |
| 5 |
Correct |
397 ms |
49276 KB |
Output is correct |
| 6 |
Correct |
450 ms |
42564 KB |
Output is correct |
| 7 |
Execution timed out |
1076 ms |
35532 KB |
Time limit exceeded |
| 8 |
Halted |
0 ms |
0 KB |
- |
