蒟蒻刚学长剖,WA求助
查看原帖
蒟蒻刚学长剖,WA求助
464004
ZepX_D楼主2024/8/2 20:54

不知道哪里错了

#include <bits/stdc++.h>
#define LL long long
#define pb push_back

using namespace std;

const int N = 1e5+5;
struct edge{int to,w,pre;}e[N<<1];
int las[N],cnt,mx,s,t,p;

void add(int u,int v,int w)
{e[++cnt] = {v,w,las[u]},las[u] = cnt;}

void D1(int x,int f,int dis)
{
	if(dis > mx) mx = dis,p = x;
	for (int i = las[x],y;i;i = e[i].pre)
		if((y = e[i].to) != f) D1(y,x,dis+e[i].w);
}

int fa[2][N],hs[2][N],h[2][N],top[2][N],dis[2][N];

void D2(int x,bool id)
{
	for (int i = las[x],y;i;i = e[i].pre)
	{
		if((y = e[i].to) != fa[id][x])
		{
			fa[id][y] = x,D2(y,id);
			if(h[id][y]+e[i].w >= h[id][x]) hs[id][x] = y,h[id][x] = h[id][y]+e[i].w;
		}
	}
}

vector < pair<int,int> > ve[2];

void D3(int x,int t,bool id)
{
	top[id][x] = t;
	if(x == t) ve[id].pb({h[id][x],x});
	if(hs[id][x]) D3(hs[id][x],t,id);
	for (int i = las[x],y;i;i = e[i].pre)
		if((y = e[i].to) != fa[id][x] && y != hs[id][x]) dis[id][y] = e[i].w,h[id][y] += e[i].w,D3(y,y,id);
}

int sum[2][N],id[2][N];

int main()
{
	ios::sync_with_stdio(0);
	int n,q;cin >> n >> q;
	for (int i = 1,u,v,w;i < n;i++)
		cin >> u >> v >> w,add(u,v,w),add(v,u,w);
	D1(1,0,0);mx = 0,s = p;D1(s,0,0);t = p;
	D2(s,0),D3(s,s,0);
	D2(t,1),D3(t,t,1);
	sort(ve[0].begin(),ve[0].end(),[](pair<int,int> a,pair<int,int> b){return a.first > b.first;});
	sort(ve[1].begin(),ve[1].end(),[](pair<int,int> a,pair<int,int> b){return a.first > b.first;});
	for (int i = 0;i < ve[0].size();i++)
		sum[0][i+1] = sum[0][i]+ve[0][i].first,id[0][ve[0][i].second] = i+1;
	for (int i = 0;i < ve[1].size();i++)
		sum[1][i+1] = sum[1][i]+ve[1][i].first,id[1][ve[1][i].second] = i+1;
	int las = 0;
	while(q--)
	{
		int x,y;cin >> x >> y;
		x = (x+las-1)%n+1,y = (y+las-1)%n+1;
		int res1 = sum[0][min(2*y-1,(int)ve[0].size())],res2 = sum[1][min(2*y-1,(int)ve[1].size())];
		if(id[0][top[0][x]] > 2*y-1)
		{
			int del = ve[0][2*y-2].first,ad = 0,p = x;
			ad += h[0][top[0][p]],p = fa[0][top[0][p]];
			while(id[0][top[0][p]] > 2*y-1)
				ad += h[0][top[0][p]]-h[0][p],p = fa[0][top[0][p]];
			del = min(del,h[0][p]-dis[0][p]);
			res1 = res1-del+ad;
		}
		if(id[1][top[1][x]] > 2*y-1)
		{
			int del = ve[1][2*y-2].first,ad = 0,p = x;
			ad += h[1][top[1][p]],p = fa[1][top[1][p]];
			while(id[1][top[1][p]] > 2*y-1)
				ad += h[1][top[1][p]]-h[1][p],p = fa[1][top[1][p]];
			del = min(del,h[1][p]-dis[1][p]);
			res2 = res2-del+ad;
		}
		cout << (las = max(res1,res2)) << '\n';
	}
	return 0;
}
2024/8/2 20:54
加载中...