CF526G Spiders Evil Plan

Description

$\rm Link$

Solution

一个题目 $\sout{114514}$ 个 $\sout{\text{trick}}$ 你值得拥有

在无根树上定义叶子为度数等于 $1$ 的点。

题目要求选 $k$ 条路径，我们考虑这样一条结论：

$2k$ 个叶子分成 $k$ 条路径，能且至多能并成它们的虚树。

可以通过构造证明：每次让 $\rm DFS$ 序最大的和最小的匹配。

于是问题转化为选择 $2k$ 个叶子。
$2k$ 个叶子同时考虑太多了，我们先只考虑选择 $1$ 个叶子。显然，这个叶子一定是直径的某个端点。

好，题目与直径扯上关系了。直径相关的题目有一个常见的 $\rm trick$ ：

如果答案一定包含直径的一个端点，那么可以把直径端点作为根考虑。

这个方法不一定能做出题目，但是值得一试。

现在我们取了直径端点作为根。接下来考虑选择 $2k-1$ 个点，使得它们包含 $x$ ，连通，并且最大化权值。
现在相当于是有两个限制，我们尝试只考虑一个限制得出一个最优化做法，再根据另一个限制来调整。

假如只有第二个限制，此时转化成了一个经典问题：

选择 $x$ 个点，满足这些点打通到根的路径后并集的权值最大。
直接长链剖分取前 $x$ 大的长链就是答案。

连通性：一条不含根的长链被选择的时间一定在其链顶的父节点所在的长链之后。
最优性：假如可以把长链改道使之更优，那么它为什么是长链呢？

于是现在我们选出来了 $2k-1$ 条长链。若 $x$ 在长链中，皆大欢喜；如果不在，我们就要调整。

考虑把 $x$ 并进来，也就是把 $x$ 所在的长链的底端，一直打通到「在选出来的 $2k-1$ 条长链中的 $x$ 最深的祖先节点」。

打通完后事实上多选了一条链，而删掉的链要么是「在选出来的 $2k-1$ 条长链中的 $x$ 最深的祖先节点」所在的长链忍痛割爱放弃原有的下行路线改道 $x$ 那一边，要么是直接放弃 $2k-1$ 条长链中最短的那一条。讨论一下就可以了。

真就山重水复疑无路，一个方法接着一个方法。单独拆开看不难，合在一起就非常 $\rm nb$。

复杂度 $\mathcal{O}(q\log_2 n)$ 。

Code

const int N = 1e5 + 233;
using namespace std;
int n, q, num;
int dep[N], head[N], nt[N << 1], to[N << 1], vl[N << 1];
struct Answer{
    int rt, cnt;
    int dep[N], mxd[N], son[N], dis[N], top[N], f[N][20];
    int Ans[N], Vrk[N];
    struct chain{
        int vl, pl;
        chain(int pl = 0, int vl = 0):
            pl(pl), vl(vl) {}
        bool operator < (const chain &b) const {
            return vl > b.vl;
        }
    }c[N];
    
    void Dfs0(int p, int fa){
        f[p][0] = fa;
        for(int i = 0; f[p][i]; ++i)
            f[p][i + 1]  = f[f[p][i]][i];
        for(int i = head[p]; i; i = nt[i]){
            int v = to[i]; if(v == fa) continue;
            dis[v] = vl[i];
            dep[v] = dep[p] + vl[i];
            Dfs0(v, p);
            if(mxd[v] + vl[i] > mxd[p])
                son[p] = v, mxd[p] = mxd[v] + dis[v];
        }
    }
    void Dfs1(int p, int tp){
        if(tp == 0)
            ++cnt, c[cnt] = chain(p, mxd[p] + dis[p]), top[p] = p;
        else top[p] = tp;
        if(son[p]) Dfs1(son[p], top[p]);
        for(int i = head[p]; i; i = nt[i]) 
            if(to[i] != son[p] and to[i] != f[p][0]) Dfs1(to[i], 0);
    }
    void Init(){
        Dfs0(rt, 0), Dfs1(rt, 0);
        sort(c + 1, c + cnt + 1);
        for(int i = 1; i <= cnt; ++i)
            Ans[i] = Ans[i - 1] + c[i].vl, Vrk[c[i].pl] = i;
    }
    int Jump(int x, int rk){
        for(int i = 19; i >= 0; --i)
            if(Vrk[top[f[x][i]]] > rk)
                x = f[x][i];
        return f[x][0];
    }
    int Solve(int x, int rk){
        int ret = Ans[min(rk, cnt)];
        if(Vrk[top[x]] <= rk) return ret;
        int v = Jump(x, rk);
        return ret + c[Vrk[top[x]]].vl + dep[f[top[x]][0]] - min(mxd[v], c[rk].vl) - dep[v];
    }
}ver0, ver1;
void predfs(int, int);
void add(int, int, int);
int main(){

    fin >> n >> q;

    for(int i = 1, u, v, w; i < n; ++i)
        fin >> u >> v >> w, add(u, v, w);
    
    int S = 1, T = 1;

    predfs(1, 0);
    for(int i = 1; i <= n; ++i)
        if(dep[i] > dep[S]) S = i;
    dep[S] = 0; predfs(S, 0);
    for(int i = 1; i <= n; ++i)
        if(dep[i] > dep[T]) T = i;
    ver0.rt = S, ver1.rt = T;
    ver0.Init(), ver1.Init();

    for(int i = 1, x, y, ans = 0; i <= q; ++i){
        fin >> x >> y;
        x = (x + ans - 1) % n + 1;
        y = (y + ans - 1) % n + 1;
        ans = max(ver0.Solve(x, 2 * y - 1), ver1.Solve(x, 2 * y - 1));
        cout << ans << '\n';
    }
    return 0;
}
void add(int x, int y, int z){
    ++num, nt[num] = head[x], head[x] = num, to[num] = y, vl[num] = z;
    ++num, nt[num] = head[y], head[y] = num, to[num] = x, vl[num] = z;
}
void predfs(int p, int fa){
    for(int i = head[p]; i; i = nt[i]){
        int v = to[i]; if(v == fa) continue;
        dep[v] = dep[p] + vl[i]; 
        predfs(v, p);
    }
}