【CF526G】Spiders Evil Plan（贪心）

题面

洛谷

CodeForces

给定一棵树，要求选择\(y\)条链，满足被链覆盖的所有点在树上联通，且\(x\)必定在联通块中。

对于每次询问最大化被链覆盖的边的权值和。

强制在线。

题解

假设我们只有一次询问，会怎么做？

显然以\(x\)为根，如果\(x\)的度数大于\(1\)，那么可以转化为选择\(2y\)个叶子节点，这样子一定存在一种方案满足链并恰好是\(x\)到这\(2y\)个节点的链的并。

如果\(x\)的度数为\(1\)的话，显然就选择\(2y-1\)个点来做上述操作。

我们发现直径的一个端点必定会被选中。

那么我们把问题转化一下，以直径\((a,b)\)的端点\(a,b\)中任意一个点为根来考虑这个问题，不妨以\(a\)为根来考虑。

首先我们选择\(y\)条链的答案就是选择\(2y-1\)个叶子节点的答案。但是还需要钦定\(x\)在方案内。

那么分类讨论一下，如果\(x\)的子树中存在一个叶子被选入了答案，那么就不用管了。

否则，我们必须替换一个点转而选择\(x\)子树中的一个叶子，加入点\(x\)的贡献我们可以很容易的算出，现在的问题转变成了如何找到删去的最小贡献。注意这里加入\(x\)之后删去每个点的贡献就会改变。

那么这样子只有两种情况，要么是删去最后一个加入答案的叶子，替换为\(x\)子树内的最深叶子。要么就是找到其祖先中第一个有叶子被选中的点，删去其中的一个儿子的贡献。

维护每次选择哪个叶子的时候，可以线段树考虑，也可以长链剖分+贪心。

#include<iostream>

#include<cstdio>

using namespace std;

#define mp make_pair

#define MAX 100100

inline int read()

{

	int x=0;bool t=false;char ch=getchar();

	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

	if(ch=='-')t=true,ch=getchar();

	while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

	return t?-x:x;

}

int n,Q,lans;

struct Line{int v,next,w;}e[MAX<<1];

int h[MAX],cnt=1;

inline void Add(int u,int v,int w){e[cnt]=(Line){v,h[u],w};h[u]=cnt++;}

#define lson (now<<1)

#define rson (now<<1|1)

#define fr first

#define sd second

int mxv,rt,p[19][MAX],dfn[MAX],low[MAX],ln[MAX],md[MAX],dep[MAX],tim;

void dfs(int u,int ff)

{

	p[0][u]=ff;ln[dfn[u]=++tim]=u;md[u]=dep[u];

	for(int i=1;i<19;++i)p[i][u]=p[i-1][p[i-1][u]];

	for(int i=h[u];i;i=e[i].next)

	{

		int v=e[i].v;if(v==ff)continue;

		dep[v]=dep[u]+e[i].w;dfs(v,u);

		md[u]=max(md[u],md[v]);

	}

	low[u]=tim;

}

pair<int,int> mx[MAX<<2];int tag[MAX<<2];

void pushup(int now){mx[now]=max(mx[lson],mx[rson]);}

void Build(int now,int l,int r)

{

	if(l==r){mx[now]=mp(dep[ln[l]],ln[l]);return;}

	int mid=(l+r)>>1;

	Build(lson,l,mid);Build(rson,mid+1,r);

	pushup(now);

}

void Modify(int now,int l,int r,int L,int R,int w)

{

	if(L<=l&&r<=R){mx[now].fr+=w;tag[now]+=w;return;}

	int mid=(l+r)>>1;

	if(L<=mid)Modify(lson,l,mid,L,R,w);

	if(R>mid)Modify(rson,mid+1,r,L,R,w);

	pushup(now);mx[now].fr+=tag[now];

}

int ans[MAX],vis[MAX];

void pre(int _rt)

{

	rt=_rt;dfs(rt,0);Build(1,1,n);

	for(int i=2;i<=n;++i)

	{

		ans[i]=ans[i-1]+mx[1].fr;

		for(int j=mx[1].sd;j&&!vis[j];j=p[0][j])

			vis[j]=i,Modify(1,1,n,dfn[j],low[j],dep[p[0][j]]-dep[j]);

	}

}

int Solve(int x,int y)

{

	y=min(y,n);if(vis[x]<=y)return ans[y];int u=x;

	for(int i=18;~i;--i)if(vis[p[i][x]]>y)x=p[i][x];

	x=p[0][x];

	return ans[y]+md[u]-dep[x]-min(dep[x],min(ans[y]-ans[y-1],md[x]-dep[x]));

}

void DFS(int u,int ff,int dep)

{

	if(dep>mxv)mxv=dep,rt=u;

	for(int i=h[u];i;i=e[i].next)

		if(e[i].v!=ff)DFS(e[i].v,u,dep+e[i].w);

}

int main()

{

	n=read();Q=read();

	for(int i=1,u,v,w;i<n;++i)u=read(),v=read(),w=read(),Add(u,v,w),Add(v,u,w);

	mxv=0;DFS(1,0,0);pre(rt);

	while(Q--)

	{

		int u=(read()+lans-1)%n+1,v=(read()+lans-1)%n+1;

		printf("%d\n",lans=Solve(u,v<<1));

	}

	return 0;

}