- 给定一棵(n)个点的无根树，每条边有一个边权。
- (q)组询问，每次给出(x,y)，求一个由(y)条路径组成的包含(x)的连通块，使得其中边权和最大。
- (n,qle10^5)
贪心的路径选择方案
显然，一条路径必然是以两个叶节点为端点的。
如果(2 imes y)大于等于叶节点个数，则我们必然能选中整棵树。否则我们选中(2 imes y)个叶节点，得到的连通块便是它们两两路径的交集。
那么其实也可以看作从一个叶节点到(2 imes y-1)个叶节点的路径交集。
可以发现，选中的叶节点中至少存在树的直径的两端点之一，所以我们只要分别假设选中这两个点的情况，建出两棵有根树，就变成了选出(2 imes y-1)个叶节点到根的路径。
然后我们考虑求出每个点子树内的长链，显然一个叶节点对应一条长链，且一个点第一次被选中肯定是因为所在长链末端的叶节点。
因此我们就知道了，选中一个叶节点，其实它的贡献就是它所在长链的边权总和（注意这里要加上链首到其父节点的边权）。
现假设我们不考虑(x)，只是贪心地选择(y)条路径，那么贪心必然选择边权总和较大的(2y-1)条长链。
那么就是要考虑这(2y-1)条长链不包括(x)的情况。
强制连通块包含(x)
简单分析之后发现只有两种把(x)放到连通块中的方案：
- 在原答案基础上，先删去最劣的长链，然后改选从(x)所在长链向上的最长的未被选择过的路径。
- 在原答案基础上，直接找到(x)所在长链向上的最长的未被选择过的路径，删去链首父节点子树内原本的贡献。
然后发现这两种方案的共性就是我们都需要找到(x)向上深度最小的未被选择过的节点，直接倍增上跳就好了。
代码：(O((n+q)logn))
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define N 100000
#define LN 18
#define LL long long
#define add(x,y,z) (e[++ee].nxt=lnk[x],e[lnk[x]=ee].to=y,e[ee].v=z)
using namespace std;
int n,rt1,rt2,ee,lnk[N+5];struct edge {int to,nxt,v;}e[N<<1];
namespace TD//树的直径
{
int q[N+5];LL dis[N+5];I int BFS(CI x)//BFS求树的直径
{
RI i,k,H=1,T=1;for(i=1;i<=n;++i) dis[i]=-1;dis[q[1]=x]=0;
RI f=0;W(H<=T) for(i=lnk[k=q[H++]];i;i=e[i].nxt)
!~dis[e[i].to]&&(dis[q[++T]=e[i].to]=dis[k]+e[i].v)>dis[f]&&(f=e[i].to);
return f;
}
I void Get(int& x,int& y) {x=BFS(1),y=BFS(x);}//记录直径两端点
}
class Tree
{
private:
int t,rk[N+5],p[N+5],g[N+5],f[N+5][LN+5];LL ans[N+5],d[N+5],w[N+5];
struct Data
{
int x;LL y;I Data(CI a=0,Con LL& b=0):x(a),y(b){}//存储链首和长链边权总和
I bool operator < (Con Data& o) Con {return y>o.y;}
}s[N+5];
I void dfs1(CI x)//第一遍dfs
{
RI i;for(i=1;i<=LN;++i) f[x][i]=f[f[x][i-1]][i-1];
for(i=lnk[x];i;i=e[i].nxt) e[i].to^f[x][0]&&
(
d[e[i].to]=d[f[e[i].to][0]=x]+e[i].v,dfs1(e[i].to),
w[e[i].to]+e[i].v>w[x]&&(w[x]=w[g[x]=e[i].to]+e[i].v)//记录长儿子和长链长度
);
}
I void dfs2(CI x,CI c)//第二遍dfs
{
(p[x]=c)==x&&(s[++t]=Data(x,w[x]+d[x]-d[f[x][0]]),0),g[x]&&(dfs2(g[x],c),0);
for(RI i=lnk[x];i;i=e[i].nxt) e[i].to^f[x][0]&&e[i].to^g[x]&&(dfs2(e[i].to,e[i].to),0);
}
public:
I void Init(CI rt)
{
dfs1(rt),dfs2(rt,rt),sort(s+1,s+t+1);
for(RI i=1;i<=t;++i) rk[s[i].x]=i,ans[i]=ans[i-1]+s[i].y;//贪心，前缀和统计前i大的长链之和
}
I LL GetAns(CI x,CI k)
{
if(rk[p[x]]<=k) return ans[k];RI u=x,v=x;
for(RI i=LN;~i;--i) rk[p[f[u][i]]]>=k&&(u=f[u][i]);//删去最劣长链上跳
for(RI i=LN;~i;--i) rk[p[f[v][i]]]>k&&(v=f[v][i]);//直接上跳
return d[x]+w[x]+max(-d[f[u][0]]+ans[k-1],-d[f[v][0]]-w[f[v][0]]+ans[k]);//两种方案取较优值
}
}T1,T2;
int main()
{
RI Qt,i,x,y,z,c=0;LL s=0,t=0;for(scanf("%d%d",&n,&Qt),i=1;i^n;++i)
scanf("%d%d%d",&x,&y,&z),s+=z,add(x,y,z),add(y,x,z);TD::Get(rt1,rt2);
for(i=1;i<=n;++i) c+=!e[lnk[i]].nxt;//求出叶节点个数
T1.Init(rt1),T2.Init(rt2);W(Qt--) scanf("%d%d",&x,&y),x=(x+t-1)%n+1,
y=(y+t-1)%n+1,printf("%lld
",t=2*y>=c?s:max(T1.GetAns(x,2*y-1),T2.GetAns(x,2*y-1)));//如果2y≥c则可以选整棵树
return 0;
}