CF526G Spiders Evil Plan 题解

题意

给定一颗 $n$ 个点的树，有边权，$q$ 次询问，每次询问用最多 $y$ 组成的包含 $x$ 的连通块的最大边权和。

思路

首先考虑贪心，每次选择当前未被选择的最长路径，那么第一次选择的一定是直径，选择的所有路径端点都是叶子节点。

则以两个直径的端点为根，题意转化为选择 $2y-1$ 个叶子节点到根的路径，使得路径最长。

考虑长链剖分，从根节点开始维护一个堆，每次选择到叶子节点最长的节点，则第 $i$ 次的路径长度即为链的长度，然后把链上所有节点的子节点放入堆中，这样动态维护就可以计算出选择 $y$ 条路径的答案。

考虑如何处理经过 $x$，加入当前的前 $2y-1$ 条长链包括 $x$，则答案即为前 $2y-1$ 条链的长度和。

否则有两种情况：

1，取前 $2y-2$ 条链以及 $x$ 本身所在的那条链加上 $x$ 到 $x$ 的深度最小且不在前 $2y-2$ 条链的祖先之间的距离。

注：图中省略了已选择的链之间的便，实际计算要加上。

红色是前 $2y-1$ 条链，绿色是被替换的链，蓝色是 $x$ 的链。

2，取前 $2y-1$ 条链以及 $x$ 本身所在的那条链加上 $x$ 到 $x$ 的深度最小且不在前 $2y-1$ 条链的祖先之间的距离，再减去祖先的父节点以下的长链即可。

这样这道题就做完了，时间复杂度为 $O(n \log n)$

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,qq;
struct N{
	int y,v;
}; 
vector<N> e[100010];
int dis[100010];
void dfs(int x,int xfa){//求直径 
	for(N i:e[x])if(i.y!=xfa){
		int y=i.y;
		dis[y]=dis[x]+i.v;
		dfs(y,x);
	}
}
int d[100010],son[100010],mx[100010],cnt,st[100010][25];
void dfs2(int x,int xfa){//长链剖分
	son[x]=-1;
	st[x][0]=xfa;
	for(int i=1;i<=20;i++)st[x][i]=st[st[x][i-1]][i-1];
	for(N i:e[x])if(i.y!=xfa){
		int y=i.y;
		d[y]=d[x]+i.v;
		if(e[y].size()==1)cnt++;
		dfs2(y,x);
		if(son[x]==-1||mx[y]+i.v>mx[x])son[x]=y,mx[x]=mx[y]+i.v;
	}
}
int d2[100010],son2[100010],mx2[100010],cnt2,st2[100010][25],p2[100010];
void dfs22(int x,int xfa){//对第二个根的长链剖分 
	son2[x]=-1;
	st2[x][0]=xfa;
	for(int i=1;i<=20;i++)st2[x][i]=st2[st2[x][i-1]][i-1];
	for(N i:e[x])if(i.y!=xfa){
		int y=i.y;
		d2[y]=d2[x]+i.v;
		if(e[y].size()==1)cnt2++;
		dfs22(y,x);
		if(son2[x]==-1||mx2[y]+i.v>mx2[x])son2[x]=y,mx2[x]=mx2[y]+i.v;
	}
}
struct Q{
	int x,v;
	bool operator<(const Q &n1)const{
		return v<n1.v;
	}
};
int p[100010],tsp,l[100010],tot[100010],l2[100010],tot2[100010];
priority_queue<Q> q;
void dfs3(int x){//将链上的所有点的子节点加入堆 
	p[x]=tsp;
	for(N i:e[x])if(!p[i.y]){
		int y=i.y;
		if(y==son[x])dfs3(y);
		else q.push({y,mx[y]+i.v});
	}
}
void dfs32(int x){
	p2[x]=tsp;
	for(N i:e[x])if(!p2[i.y]){
		int y=i.y;
		if(y==son2[x])dfs32(y);
		else q.push({y,mx2[y]+i.v});
	}
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n>>qq;
	for(int i=1,x,y,v;i<n;i++){
		cin>>x>>y>>v;
		e[x].push_back({y,v});
		e[y].push_back({x,v});
	}
	dfs(1,0);
	int rt=1;
	for(int i=1;i<=n;i++)if(dis[i]>dis[rt])rt=i;
	dfs2(rt,0);
	q.push({rt,mx[rt]});
	for(int _=1;_<=cnt;_++){//长链剖分 
		int x=q.top().x,v=q.top().v;
		q.pop();
		tsp++;
		l[tsp]=v;
		dfs3(x);
	}
	for(int i=1;i<=cnt+1;i++){
		tot[i]=tot[i-1]+l[i];
	}
	dfs(rt,0);
	int rt2=1;
	for(int i=1;i<=n;i++)if(dis[i]>dis[rt2])rt2=i;
	while(!q.empty())q.pop(); 
	dfs22(rt2,0);
	q.push({rt2,mx2[rt2]});
	tsp=0;
	for(int _=1;_<=cnt;_++){
		int x=q.top().x,v=q.top().v;
		q.pop();
		tsp++;
		l2[tsp]=v;
		dfs32(x);
	}
	for(int i=1;i<=cnt+1;i++){
		tot2[i]=tot2[i-1]+l2[i];
	}
	int la=0;
	while(qq--){
		int x,y;
		cin>>x>>y;
		x=(x+la-1)%n+1;
		y=(y+la-1)%n+1;
		y=2*y-1;
		y=min(y,cnt+1);
		int ans=0;
		if(p[x]<=y)ans=max(ans,tot[y]);
		else{
			int u=x;
			for(int i=20;~i;i--)if(p[st[u][i]]>y)u=st[u][i];
			ans=max(ans,max(tot[y-1]+d[x]-d[st[u][0]]+mx[x],tot[y]-mx[st[u][0]]+d[x]-d[st[u][0]]+mx[x]));
		} 
		if(p2[x]<=y)ans=max(ans,tot2[y]);
		else{
			int u=x;
			for(int i=20;~i;i--)if(p2[st2[u][i]]>y)u=st2[u][i];
			ans=max(ans,max(tot2[y-1]+d2[x]-d2[st2[u][0]]+mx2[x],tot2[y]-mx2[st2[u][0]]+d2[x]-d2[st2[u][0]]+mx2[x]));
		} 
		cout<<(la=ans)<<'\n';
	}
	return 0;
}