# 某岛

… : "…アッカリ～ン . .. . " .. .
April 4, 2020

## UOJ #55. 【WC2014】紫荆花之恋

LCA 的代码复制 这里
SBT 的代码复制 这里

http://uoj.ac/submission/391176

```const int N = int(1e5) + 9, M = 2*N, NN = 50*N, LV = 17;

namespace Raw_Tree {

int hd[N], prd[M], suc[M], to[M]; int ww[N];
int n, en;

inline void add_edge(int x, int y) {
suc[prd[hd[x]] = en] = hd[x]; to[en] = y; hd[x] = en++;
suc[prd[hd[y]] = en] = hd[y]; to[en] = x; hd[y] = en++;
}
inline void del(int i){
if (i == hd[to[i^1]]) prd[hd[to[i^1]] = suc[i]] = 0;
else prd[suc[i]] = prd[i], suc[prd[i]] = suc[i];
}
inline void rec(int i) {
if (suc[i] == hd[to[i^1]]) hd[to[i^1]] = prd[suc[i]] = i;
else suc[prd[i]] = prd[suc[i]] = i;
}

int dep[N], dis[N], fa[N][17];
void add(int u, int p, int w) {
dep[u] = dep[p] + 1; dis[u] = dis[p] + w;
fa[u][0] = p; for (int lv=0;fa[u][lv+1]=fa[fa[u][lv]][lv];++lv);
}
inline int move_up(int x, int t){
for (int lv=0;t;++lv,t>>=1)
if (t&1) x = fa[x][lv];
return x;
}
inline int lca(int x, int y) {
if (dep[x]>dep[y]) swap(x,y); y=move_up(y, dep[y]-dep[x]); if (x==y) return x;
DWN(lv, LV, 0) if (fa[x][lv]^fa[y][lv]) x = fa[x][lv], y = fa[y][lv];
return fa[x][0];
}
inline int dist(int x, int y) {
return dis[x] + dis[y] - 2*dis[lca(x,y)];
}
} using namespace Raw_Tree;

namespace SBT {

int c[2][NN], sz[NN], ky[NN];
#define l c[d]
#define r c[!d]
#define lx l[x]
#define rx r[x]
#define kx ky[x]
#define sx sz[x]
#define d 0
stack<int> pool;
int new_node(int v = 0){
int x=pool.top();pool.pop();lx=rx=0;
sx=1;kx=v;
return x;
}
void upd(int x){
sx=sz[lx]+1+sz[rx];
}
#undef d
void rot(int &x,int d){
int y=rx;rx=l[y];l[y]=x;
upd(x),upd(y),x=y;
}
void fix(int &x,int d){
if (sz[l[lx]] > sz[rx]) rot(x,!d);
else{
if (sz[r[lx]] > sz[rx]) rot(lx,d),rot(x,!d);
else return;
}
d=0,fix(lx,0),fix(rx,1);
fix(x,0),fix(x,1);
}
#define d 0
void Ins(int &x,int v){
if(!x) x = new_node(v);
else{
++sz[x]; Ins(c[v>kx][x],v);
fix(x,v>=kx);
}
}
int d_key; void Del(int &x,int v){
--sx;if(kx==v||(v<kx&&!lx)||(v>kx&&!rx)){
if(!lx||!rx) d_key = kx, x = lx | rx;
else Del(lx,v+1), kx = d_key;
}
else Del(c[v>kx][x],v);
}

int Rank(int x,int v) {
int z=0;while(x){
if(kx<=v){
z+=sz[lx]+1;
x=rx;
} else{
x=lx;
}
}
return z;
}
void clean(int& x) {
if (!x) return;
clean(lx); clean(rx);
pool.push(x);
x = 0;
}
#undef d
#undef sx
#undef kx
#undef lx
#undef rx
#undef l
#undef r
};

int r[N];

namespace TDC {
int T0[N], T1[N];
int fa[N], sz[N], nn, cc, c;

void clean(int u) {
vis[u] = time; SBT::clean(T0[u]);
SBT::clean(T1[v]);
clean(v);
}
}

#define v to[i]
#define w ww[i/2]
void dfsc(int u, int p = 0){
int ss = 0; sz[u] = 1; REP_G(i, u) if (v != p){
if (vis[v] != time) continue;
dfsc(v, u), sz[u] += sz[v];
checkMax(ss, sz[v]);
}
checkMax(ss, nn - sz[u]);
if (ss <= cc) cc = ss, c = u;
}

void dfs0(int u, int p, int d, int& T) {
SBT::Ins(T, d - r[u]);
REP_G(i, u) if (v != p) {
if (vis[v] != time) continue;
dfs0(v, u, d+w, T);
}
}
int divide(int u) {
cc = nn; dfsc(u); u = c;
dfs0(u, 0, 0, T0[u]);
REP_G(i, u) {
if (vis[v] != time) continue;
del(i^1); int t = 0; dfs0(v, 0, w, t);
nn = sz[v]; int vv = divide(v);
rec(i^1); fa[vv] = u; adj[u].insert(vv); T1[vv] = t;
}
return u;
}
#define p fa[u]
void rebuild(int u) {
int pp = p, tt = T1[u];
++time; nn = SBT::sz[T0[u]]; clean(u);
T1[u] = tt;
}
LL add_leaf(int uu, int pp) {
int u = uu;
LL z = 0; pp = 0;
for (;u;u=p) {
if (p) {
int d = dist(p, uu);
z += SBT::Rank(T0[p], r[uu] - d);
z -= SBT::Rank(T1[u], r[uu] - d);
SBT::Ins(T1[u], d - r[uu]);
if (SBT::sz[T0[u]] > SBT::sz[T0[p]] * 0.75) pp = p;
}
int d = dist(u, uu);
SBT::Ins(T0[u], d - r[uu]);
}
if (pp) rebuild(pp);
return z;
}
#undef p
#undef v
#undef w
};

int main() {

#ifndef ONLINE_JUDGE
//freopen("/Users/minakokojima/Documents/GitHub/ACM-Training/Workspace/in.txt", "r", stdin);
//freopen("/Users/minakokojima/Documents/GitHub/ACM-Training/Workspace/out.txt", "w", stdout);
#endif

#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif

DWN(i, NN, 1) SBT::pool.push(i);

scanf("%*d%d", &n); REP_1(u, n) {
int p, w; RD(p, w); RD(r[u]); p ^= last_ans % 1000000000; add(u, p, w);