题解：P10301 [THUWC 2020] Yazid 的棋

可以当作 LCT 维护动态基环树的模板。

为了保证了每个点都一定有恰好一条出边，可以强制添加 n 条 i\to i 的自环，边权 +\infty，编号 +\infty。

需要动态维护环，但正常的数据结构显然不能直接做这个工作。考虑对每个环钦定一个环上的点断掉其出边，其他的边按树的方法维护。

为了方便判断，可以钦定 LCT 上每一个连通块的根都是被断开的点。（需要注意，这会导致在代码中不能随便 makeroot）

由于每条边都有对应的一个点，可以将边权直接记在入点上。

模拟题目跳边的过程，根据一些 trivial 的分析我们只需要找到第一次断边发生的时刻，或 s=0 的时刻即可。

这时需要的操作是：

• 求到根链上最小权值。
• 到根链上所有点 val := val- z（模拟在环上跳很多圈的过程）。
• 二分出到根链上最深的 val=1 的点（需要断边的点）。

access 一下，就是 splay 的经典操作了，这里不再赘述。重点关注断边（换边）的过程：

• 断掉的是树边：
  • 直接对父亲 access 后清空父亲即可。
  • 若新边连向另一个连通块，则新边仍是树边，直接连接。
  • 否则新边是环边，这个点直接成为根（不需要任何操作）。
• 断掉的是环边：
  • 若该点是根，直接修改新边，和上面的情况类似。
  • 否则需要先断掉该边，再插入根的边，然后也和上面的情况类似了，分有没有连向新连通块讨论即可。

判断 x 是否在环上的方法：检查 x 与 next(root) 的 LCA 是否是 x 即可。

其余就是 LCT 的基础操作了。思路理清楚代码还是很好写的。

复杂度 O((n+m)\log n)。

#define N 200010
int n, m;
int u_[N], v_[N], w_[N];
int h[N], e[N << 1], v[N << 1], ne[N << 1], idx = -1;
void add_edge(int x, int y, int z) { ne[++idx] = h[x], h[x] = idx, e[idx] = y, v[idx] = z; }
struct Tree
{
    int mn, val, mnlazy;
    int ch[2], fa, sz;
    void pushmn(int z) { mn -= z, val -= z; mnlazy += z; }
}tr[N];
#define lson(k) tr[k].ch[0]
#define rson(k) tr[k].ch[1]
#define son(k, i) tr[k].ch[i]
#define fa(k) tr[k].fa
void pushup(int k) { tr[k].mn = std::min({tr[lson(k)].mn, tr[rson(k)].mn, tr[k].val}); tr[k].sz = tr[lson(k)].sz + tr[rson(k)].sz + 1; }
void pushdown(int k) { if(tr[k].mnlazy) { if(lson(k)) tr[lson(k)].pushmn(tr[k].mnlazy); if(rson(k)) tr[rson(k)].pushmn(tr[k].mnlazy); tr[k].mnlazy = 0; } }
int getid(int k) { return rson(fa(k)) == k; }
int notroot(int k) { return lson(fa(k)) == k || rson(fa(k)) == k; }
void rotate(int k)
{
    int f = fa(k), gf = fa(f), id = getid(k), fid = getid(f), bro = son(k, id ^ 1);
    if(notroot(f)) son(gf, fid) = k;
    son(f, id) = bro; fa(bro) = f;
    son(k, id ^ 1) = f; fa(f) = k;
    fa(k) = gf; pushup(f); pushup(k);
}
void splay(int k)
{
static int sta[N], top;
    for(int p = sta[top = 1] = k; notroot(p); sta[++top] = p = fa(p));
    for(; top; pushdown(sta[top--]));
    for(; notroot(k); rotate(k)) if(notroot(fa(k))) rotate(getid(k) == getid(fa(k)) ? fa(k) : k);
}
int access(int k) { int nx = 0; for(; k; k = fa(nx = k)) { splay(k); rson(k) = nx; pushup(k); } return nx; }
int findroot(int k)
{
    access(k); splay(k);
    while(lson(k)) k = lson(k), pushdown(k);
    splay(k); return k;
}

bool vis[N];
std::vector <int> vec[N];
void dfs0(int k, int fa)
{
    fa(k) = fa; vis[k] = 1;
    for(int nx : vec[k]) if(!vis[nx]) dfs0(nx, k);
}
void changeedge(int x, int rt)
{
    access(e[h[rt]]); int p = access(x); splay(x);
    if(x != rt) 
    {  
        access(e[h[x]]); splay(x);
        fa(x) = 0; 
    }
    h[x] = ne[h[x]];
    if(x == p && x != rt)
        splay(rt), fa(rt) = e[h[rt]];
    int q = findroot(e[h[x]]);
    if(q != x) 
    {
        splay(x);
        fa(x) = e[h[x]];
    }
    splay(x); tr[x].val = v[h[x]]; pushup(x);
}
pii dividemn(int x)
{
    if(tr[x].mn > 1) return mkp(0, 0);
    int sz = 0;
    while(1)
    {
        pushdown(x);
        if(rson(x) && tr[rson(x)].mn == 1) sz += tr[lson(x)].sz + 1, x = rson(x);
        else if(tr[x].val == 1) return mkp(x, sz + 1 + tr[lson(x)].sz);
        else x = lson(x);
    }
    debug("???\n");
    return mkp(0, 0);
}
void upd(int x, int d)
{
    if(!x || d <= 0) return;
    if(d >= tr[x].sz) { tr[x].pushmn(1); return; }
    pushdown(x);
    upd(rson(x), d); d -= tr[rson(x)].sz;
    if(d > 0) d--, tr[x].val--;
    upd(lson(x), d);
    pushup(x);
}
int jump(int x, int d)
{
    while(1)
    {
        pushdown(x);
        if(d <= tr[rson(x)].sz) { x = rson(x); continue; }
        d -= tr[rson(x)].sz;
        if(d == 1) return x;
        d--;
        x = lson(x);
    }
}
int calc(int x, int d)
{
    if(!d) return x;
    int rt = findroot(x);
    access(x); splay(x);
    if(x == e[h[rt]])
    {
        int t = std::min(d / tr[x].sz, tr[x].mn - 1);
        tr[x].pushmn(t); d -= t * tr[x].sz;
    }
    if(!d) return x;
    pii t = dividemn(x);
    if(t.fi)
    {
        upd(x, std::min(d, tr[x].sz - t.se));
        if(tr[x].sz - t.se < d) { d -= tr[x].sz - t.se; int nxt = e[h[t.fi]]; changeedge(t.fi, rt); return calc(nxt, d - 1); }
        else return e[h[jump(x, d)]];
    }
    upd(x, std::min(d, tr[x].sz)); 
    if(tr[x].sz < d) { d -= tr[x].sz; return calc(e[h[rt]], d); }
    else return e[h[jump(x, d)]];
}

void solve()
{
    tr[0].mn = inf;
    memset(h, idx = -1, sizeof(h));
    n = read(), m = read();
    for(int i = 1; i <= m; i++) u_[i] = read(), v_[i] = read(), w_[i] = read();
    for(int i = 1; i <= n; i++) add_edge(i, i, inf);
    for(int i = m; i >= 1; i--) add_edge(u_[i], v_[i], w_[i]);

    for(int i = 1; i <= n; i++) vec[e[h[i]]].push_back(i);
    for(int i = 1; i <= n; i++) if(!vis[i])
    {
        int p = i; for(; !vis[p]; vis[p] = 1, p = e[h[p]]);
        for(int k = i; vis[k]; vis[k] = 0, k = e[h[k]]);
        dfs0(p, 0);
    }
    for(int i = 1; i <= n; i++) tr[i].val = tr[i].mn = v[h[i]], tr[i].sz = 1;

    m = read();
    for(int i = 1; i <= m; i++)
    {
        int x = read(), d = read();
        print(calc(x, d), '\n');
    }
}