CF526G Spiders Evil Plan 题解

题意：

二次魔改自 link

最近 q779 迷上了一个叫做割绳子 3 的~~yúsì~~（游戏）。

这个游戏的要求是你要扮演蜘蛛去吃掉一个糖果。

那是一个像割绳子游戏一样的界面，共有 \(n\) 个节点，和 \(n-1\) 条有长度的边，组成了一个树状结构。一共有 \(q\) 关，第 \(i\) 关，糖果在第 \(x_i\) 个节点上，共有 \(y_i\) 只蜘蛛。

每只蜘蛛可以用它的网去覆盖任意不同两点 \(a\) 和 \(b\) 之间的路径，因此，\(y\) 只蜘蛛可以覆盖 \(y\) 条树上路径的并。当然，不同的蜘蛛选择的路径可以相交。并且，具有如下的要求：

\(y\) 条路径必须包含糖果所在的节点 \(x\)。

\(y\) 条路径的并是连通的。

使 \(y\) 条路径所经过的边的长度总和最大。

可是蜘蛛们好像都非常智障，所以它们需要你帮忙求出最大值。

本题强制在线 ，数据范围： \(1 \le x_i,y_i \le n,~1\le n,q \le 10^5\)

关键词：贪心、树剖、树的直径

先不考虑 \(x\) 的存在，直接去选这样的路径并

肯定是这样子的

\(y=1\) ，选直径
\(y=2\) ，选 \(y=1\) 的再加一个最大的分支
\(y=3\) ，选 \(y=2\) 的再加一个剩下的最大分支
\(\cdots\)

因此可以把直径的一个端点当作根 \(\mathtt{rt}\) ，然后去跑个重链剖分（树剖）

然后在所有切出的链中找最优的 \(2y-1\) 条链

注：下文中的链均指树剖后的链

为什么是 \(2y-1\) 条链？怎么最优？

首先每条切出来的链一定包含叶子结点，从重链剖分的性质可以得出

那么就是选 \(2y-1\) 个叶子，\(-1\) 是因为根节点必选，但它不是叶子。

而两两叶子对应的链可以通过根节点并成一条链，显然这是优的。

考虑两两叶子的全序关系。我们令 \(\mathtt{len}_i\) 表示叶子 \(i\) 对应的链的长度

显然我们选的一定是 \(\mathtt{len}_i\) 最大的 \(2y-1\) 个叶子。

现在考虑 \(x\) 的情况

记 \(\mathtt{rnk}_i\) 表示按 \(\mathtt{len}_i\) 降序排序后的叶子 \(i\) 的排名

如果 \(x\) 在最优方案中已经被选了，即 \(\mathtt{rnk}_x \le 2y-1\) ，那么直接输出即可

如果 \(x\) 不在最优方案中，考虑两种方案的最优者

把 \(\mathtt{rnk}_{2y-1}\) 扔了，把 \(i\) 加进去
把 \(i\) 到 \(\mathtt{rt}\) 的路径找出来，取其中深度最大的一个结点 \(\delta\)

使得 \(\delta\) 在原最优方案中被选了，然后把 \(\delta\) 下面原来连的砍了(害怕)，把它与 \(x\) 接上。

这个可以用倍增数组来 \(O(\log n)\) 查。

然后会发现第二行在 \(y=1\) 的情况就挂了

事实上只有 \(y=1\) 会挂。特判即可。

为什么呢？因为 \(y=1\) 时的最优方案不一定会把 \(\mathtt{rt}\) 选进去

稍微因此有点区别。我们还是找到这样的 \(\delta\)

然后尝试把它与直径另一端连一下

可以证明，这样一定是最优的

然后这题就没了，恭喜您做出了Codeforces评分3300的题目 Orz

时间复杂度 \(O(Q \log n)\) ，因为链数与 \(\Theta(\log n)\) 同阶，对复杂度影响不大

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cstdarg>
#include <cmath>
#include <iomanip>
#include <random>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N ((int)(1e5+15))
#define M ((int)(2e5+15))
#define LN 18

struct Edge{int u,v,w,next;} e[M];
int n,rt,pos=1,ccnt,head[N],dep[N],fa[N],sum[N];
int grd[N],len[N],rnk[N],sz[N],chain[N],son[N],top[N],q[N][LN];
void up(int &x,int y){ x = ( x > y ) ? x : y;}
void down(int &x,int y) { x =  ( x > y ) ? y : x;}
void addEdge(int u,int v,int w)
{
    e[++pos]={u,v,w,head[u]};
    head[u]=pos;
}
void dfs1(int u,int Fa)
{
    if(dep[u] > dep[rt]) rt=u;
    for(int i=head[u],v; i; i=e[i].next)
    {
        if((v=e[i].v) != Fa)
            dep[v] = dep[u] + e[i].w, dfs1(v,u);
    }
}
void dfs2(int u)
{
    int mx=-1;
    for(int i=head[u],v; i; i=e[i].next)
    {
        if((v=e[i].v) != fa[u])
        {
            fa[v] = u; dep[v] = dep[u] + e[i].w;
            dfs2(v); up(sz[u], sz[v] + e[i].w);
            sz[v] + e[i].w > mx ? (son[u] = v, mx = sz[v] + e[i].w ): 0;
        }
    }
}
void dfs3(int u,int ftop)
{
    top[u] = ftop;
    if(u == ftop)
        {q[u][0] = top[fa[u]]; for(int i=0; q[u][i]; i++) q[u][i+1]=q[q[u][i]][i];}
    grd[u] = (ftop == rt ? u : grd[fa[u]]);
    if(!son[u]) return len[ftop] += dep[u] - dep[ftop], void(0);
    dfs3(son[u], ftop);
    for(int i=head[u],v; i; i=e[i].next)
        if(!top[v=e[i].v]) len[v] = e[i].w, dfs3(v,v);
}
int qry(int u,int r)
{
    for(int i=LN-1; i>=0; i--)
        if(q[u][i] && rnk[q[u][i]] >= r) u = q[u][i];
    return u;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int Q; cin >> n >> Q;
    for(int i=1,u,v,w; i<n; i++)
        cin >> u >> v >> w, addEdge(u,v,w), addEdge(v,u,w);
    dfs1(1,0); dep[rt]=0; dfs2(rt); dfs3(rt,rt);
    for(int i=1; i<=n; i++) if(top[i] == i) chain[ccnt++]=i;
    sort(chain, chain + ccnt, [] (int x,int y) {return len[x]>len[y];});
    for(int i=0; i<ccnt; i++) rnk[chain[i]]=i, sum[i+1] = sum[i] + len[chain[i]];
    for(int u,v,m,ans=0; Q--; )
    {
        cin >> v >> m; ans%=n;
        v = (v + ans - 1) % n + 1; m = (m + ans - 1) % n * 2 + 1;
        if(rnk[top[v]] < m) ans=sum[min(m,ccnt)];
        else
        {
            u=fa[qry(top[v],m)];
            up(ans=sum[m-1], sum[m]-min(sz[u], dep[grd[u]]));
            ans += dep[v] - dep[u] + sz[v];
        }
        cout << ans << '\n';
    }
    return 0;
}