#include <bits/stdc++.h>
using namespace std;
typedef long long 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[70005];
ll depth[70005];
set<ll>exo[70005][2][2];
ll timi[70005][2];
void build(ll idx,ll p){
an[idx][0] = p;
f(j,1,20){
an[idx][j] = an[an[idx][j-1]][j-1];
}
par[idx] = p;
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){
assert(depth[B] != depth[a]);
b = kth(B,depth[B] - depth[a] - 1);
exo[b][m][0].insert(c);
exo[B][m][1].insert(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[b][m][0].insert(c);
exo[a][m][0].insert(c);
exo[B][m][1].insert(c);
exo[A][m][1].insert(c);
}
set<ll>cur[2];
void solve(ll idx,ll p){
f(j,0,2){
for(auto x:exo[idx][j][0]){
cur[j].insert(x);
}
}
timi[idx][0] = (*cur[0].rbegin());
timi[idx][1] = (*cur[1].begin());
f(j,0,2){
for(auto x:exo[idx][j][1]){
cur[j].erase(x);
}
}
for(auto x:adj[idx]){
if(x != p){
solve(x,idx);
}
}
f(j,0,2){
for(auto x:exo[idx][j][1]){
cur[j].insert(x);
}
}
f(j,0,2){
for(auto x:exo[idx][j][0]){
cur[j].erase(x);
}
}
}
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;
assert(z > 0);
lca(x,y,c == 'M',z);
}
cur[1].insert(1e9+7);
cur[0].insert(0);
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){
ex.insert(ii(x.S,x.F));
}
while(!ex.empty()){
auto it = ex.begin();
ii f = (*it);
if(f.F == 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<<" "<<par[i]<<" "<<val<<"\n";
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
13396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
218 ms |
45820 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
124 ms |
38972 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
13396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
