题目大意：
给出一个$n(n\leq 10^5)$个结点的带边权的树，$q(q\leq 10^5)$个询问，每次询问用$y$条路径覆盖整棵树且覆盖$x$至少一次，最多能覆盖的道路长度是多少？
强制在线。
思路：
考虑固定$x$时的情况，我们可以使用长链剖分，然后贪心地选择$2y$条长链，每$2$条可以组成一条路径，这样就找出了$y$条路径的最优方案，均摊复杂度$O(n)$。
现在考虑$x$不固定的情况，对于每个询问分别做一次长链剖分，复杂度是$O(nq)$的，显然会超时。
考虑如何只用一次树剖解决所有的询问。
问题也就变成了如何确定一个根，使得所有询问的覆盖方案中，每条路径都会经过这个根。
显然，经过一点最长的路径肯定会经过直径的一个端点。
因此我们可以将直径的任一端点作为根结点开始树剖，然后贪心地选$2y-1$条最长链（最长的一条本身就是一条路径），这样时间复杂度就是$O(n+q)$。
但是这样并不是完全正确的，因为$2y-1$条最长链不一定能涵盖$x$。
因此我们需要将其中一条替换成一条经过$x$的链。
具体分为以下三种情况：
1.直接把最短的一整条链去掉；
2.把从根结点出发的一条链去掉上面一半；
3.把离$x$最近的一条链去掉下面$y$一半。
#include<queue>
#include<cstdio>
#include<cctype>
#include<vector>
#include<algorithm>
inline int getint() {
register char ch;
while(!isdigit(ch=getchar()));
register int x=ch^'';
while(isdigit(ch=getchar())) x=(((x<<)+x)<<)+(ch^'');
return x;
}
const int N=;
struct Edge {
int to,w;
};
bool vis[N];
std::queue<int> q;
std::vector<Edge> e[N];
int dis[N],far[N],par[N],top[N],son[N],leaf[N],rank[N],sum[N],root;
inline void add_edge(const int &u,const int &v,const int &w) {
e[u].push_back((Edge){v,w});
e[v].push_back((Edge){u,w});
}
inline void bfs() {
q.push(root=);
vis[]=true;
while(!q.empty()) {
const int x=q.front();
q.pop();
if(dis[x]>dis[root]) root=x;
for(register unsigned i=;i<e[x].size();i++) {
const int &y=e[x][i].to,&w=e[x][i].w;
if(vis[y]) continue;
dis[y]=dis[x]+w;
vis[y]=true;
q.push(y);
}
}
dis[root]=;
}
void dfs1(const int &x,const int &par) {
son[x]=;
::par[x]=par;
far[x]=dis[x];
for(unsigned i=;i<e[x].size();i++) {
const int &y=e[x][i].to,&w=e[x][i].w;
if(y==par) continue;
dis[y]=dis[x]+w;
dfs1(y,x);
if(far[y]>far[x]) {
far[x]=far[y];
son[x]=y;
}
}
}
void dfs2(const int &x) {
if(x==son[par[x]]) {
top[x]=top[par[x]];
} else {
top[x]=x;
}
if(son[x]) {
dfs2(son[x]);
} else {
leaf[++leaf[]]=x;
}
for(unsigned i=;i<e[x].size();i++) {
const int &y=e[x][i].to;
if(y==par[x]||y==son[x]) continue;
dfs2(y);
}
}
inline bool cmp(const int &x,const int &y) {
return dis[x]-dis[par[top[x]]]>dis[y]-dis[par[top[y]]];
}
inline int query(const int &x,const int &y) {
if(rank[top[x]]<=y*-) {
return sum[std::min(y*-,leaf[])];
}
int u=x;
while(rank[top[u]]>y*-) {
u=par[top[u]];
}
return sum[y*-]-std::min(std::min(sum[y*-]-sum[y*-],far[u]-dis[u]),dis[u])+(far[x]-dis[u]);
}
int main() {
const int n=getint(),q=getint();
for(register int i=;i<n;i++) {
const int u=getint(),v=getint(),w=getint();
add_edge(u,v,w);
}
bfs();
dfs1(root,);
dfs2(root);
std::sort(&leaf[],&leaf[+leaf[]],cmp);
for(register int i=;i<=leaf[];i++) {
rank[top[leaf[i]]]=i;
sum[i]=sum[i-]+dis[leaf[i]]-dis[par[top[leaf[i]]]];
}
for(register int i=,ans=;i<q;i++) {
const int x=(getint()+ans-)%n+,y=(getint()+ans-)%n+;
printf("%d\n",ans=query(x,y));
}
return ;
}