#include <iostream>
#include <unordered_set>
#include <algorithm>
#include <vector>
using namespace std;
using pii = pair<int,int>;
const int N_MAX = 7e4, L_LMT = 17, INF = 1e9+1;
const pii DFLT = {0,INF};
int N, K, P[N_MAX+2][L_LMT+2], L[N_MAX+2], C[N_MAX+2], H[N_MAX+2], R[N_MAX+2];
pii A[N_MAX+2];
vector<int> edges[N_MAX+2];
struct Segtree {
int prnt, flv, cnt;
vector<int> arr;
vector<pii> tree;
void build() {
int tsize = 1<<(33-__builtin_clz(arr.size()));
tree.resize(tsize,DFLT);
}
void add(int u) {
arr.push_back(u);
prnt = P[u][0];
flv = L[u];
++cnt;
}
pii apply(int n, pii v=DFLT) {
pii& nd = tree[n];
return nd = {max(nd.first,v.first),min(nd.second,v.second)};
}
void prop(int n) {
apply(n*2,tree[n]);
apply(n*2+1,tree[n]);
}
void _update(int kl, int kr, pii v, int l=0, int r=-1, int n=1) {
if (r < 0) r = cnt-1;
if (kl > r || kr < l) return;
if (kl <= l && kr >= r) apply(n,v);
else {
prop(n);
int m = (l+r)/2;
_update(kl,kr,v,l,m,n*2);
_update(kl,kr,v,m+1,r,n*2+1);
}
}
void update(bool q, int v, int kr, int kl=-1) {
if (kl < 0) kl = flv;
else kl++;
_update(kl-flv, kr-flv, q ? pii({0,v}) : pii({v,INF}));
}
void bulkApply(int l=0, int r=-1, int n=1) {
if (r < 0) r = cnt-1;
if (l == r) A[arr[cnt-l-1]] = tree[n];
else {
prop(n);
int m = (l+r)/2;
bulkApply(l,m,n*2);
bulkApply(m+1,r,n*2+1);
}
}
};
vector<Segtree> paths;
unordered_set<int> st;
int init(int u=1, int l=1) {
int mxv = 0;
L[u] = l;
for (int v : edges[u]) {
if (L[v]) continue;
P[v][0] = u;
for (int i = 1; P[v][i-1]; ++i)
P[v][i] = P[P[v][i-1]][i-1];
if (C[u]) paths.push_back(Segtree());
if (C[mxv] < init(v,l+1)) mxv = v;
C[u] += C[v];
}
H[u] = mxv ? H[mxv] : paths.size()-1;
paths[H[u]].add(u);
return ++C[u];
}
int getAnsc(int u, int n) {
for (int i = 0; n; n >>= 1, ++i) {
if (n&1) u = P[u][i];
}
return u;
}
int getLca(int a, int b) {
if (L[a] > L[b]) swap(a,b);
b = getAnsc(b,L[b]-L[a]);
if (a == b) return a;
int ans = a;
for (int i = 32-__builtin_clz(L[a]); i >= 0; --i) {
if (P[a][i] == P[b][i]) ans = P[a][i];
else a = P[a][i], b = P[b][i];
}
return ans;
}
void update(bool q, int v, int x, int y, bool lca=0) {
if (L[x] > L[y]) swap(x,y);
if (!lca) {
int lca = getLca(x,y);
if (lca != x) update(q,v,lca,x,1);
update(q,v,lca,y,1);
} else {
while (H[x] != H[y]) {
paths[H[y]].update(q,v,L[y]);
y = paths[H[y]].prnt;
}
paths[H[y]].update(q,v,L[y],L[x]);
}
}
bool exist(int z) {
return st.find(z) != st.end();
}
int solve(int u=1) {
for (int v : edges[u]) {
if (v == P[u][0]) continue;
st.insert(R[v]=solve(v));
}
auto [m,M] = A[u];
if (M == INF || exist(M)) return m;
if (m == 0 || exist(m)) return M;
if (P[u][0]) {
auto [pm,pM] = A[P[u][0]];
if (M == pM) return m;
if (m == pm) return M;
}
return m;
}
int main() {
cin.tie(0)->ios::sync_with_stdio(0);
cin >> N;
for (int n = 1, a, b; n < N; ++n) {
cin >> a >> b;
edges[a].push_back(b);
edges[b].push_back(a);
}
paths.push_back(Segtree());
init();
for (auto& p : paths) p.build();
cin >> K;
char q; int x, y, z;
while (K--) {
cin >> q >> x >> y >> z;
update(q=='M',z,x,y);
}
for (auto& p : paths) p.bulkApply();
solve();
for (int n = 2; n <= N; ++n) {
cout << n << " " << P[n][0] << " " << R[n] << "\n";
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
4696 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
100 ms |
28104 KB |
Output is correct |
| 2 |
Correct |
98 ms |
26040 KB |
Output is correct |
| 3 |
Correct |
104 ms |
25048 KB |
Output is correct |
| 4 |
Correct |
95 ms |
28200 KB |
Output is correct |
| 5 |
Correct |
100 ms |
25028 KB |
Output is correct |
| 6 |
Correct |
85 ms |
23836 KB |
Output is correct |
| 7 |
Correct |
90 ms |
22536 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
57 ms |
22452 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
4696 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
