题目大意：
给出一个$n(nleq 10^5)$个结点的带边权的树，$q(qleq 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$一半。
1 #include<queue> 2 #include<cstdio> 3 #include<cctype> 4 #include<vector> 5 #include<algorithm> 6 inline int getint() { 7 register char ch; 8 while(!isdigit(ch=getchar())); 9 register int x=ch^'0'; 10 while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0'); 11 return x; 12 } 13 const int N=100001; 14 struct Edge { 15 int to,w; 16 }; 17 bool vis[N]; 18 std::queue<int> q; 19 std::vector<Edge> e[N]; 20 int dis[N],far[N],par[N],top[N],son[N],leaf[N],rank[N],sum[N],root; 21 inline void add_edge(const int &u,const int &v,const int &w) { 22 e[u].push_back((Edge){v,w}); 23 e[v].push_back((Edge){u,w}); 24 } 25 inline void bfs() { 26 q.push(root=1); 27 vis[1]=true; 28 while(!q.empty()) { 29 const int x=q.front(); 30 q.pop(); 31 if(dis[x]>dis[root]) root=x; 32 for(register unsigned i=0;i<e[x].size();i++) { 33 const int &y=e[x][i].to,&w=e[x][i].w; 34 if(vis[y]) continue; 35 dis[y]=dis[x]+w; 36 vis[y]=true; 37 q.push(y); 38 } 39 } 40 dis[root]=0; 41 } 42 void dfs1(const int &x,const int &par) { 43 son[x]=0; 44 ::par[x]=par; 45 far[x]=dis[x]; 46 for(unsigned i=0;i<e[x].size();i++) { 47 const int &y=e[x][i].to,&w=e[x][i].w; 48 if(y==par) continue; 49 dis[y]=dis[x]+w; 50 dfs1(y,x); 51 if(far[y]>far[x]) { 52 far[x]=far[y]; 53 son[x]=y; 54 } 55 } 56 } 57 void dfs2(const int &x) { 58 if(x==son[par[x]]) { 59 top[x]=top[par[x]]; 60 } else { 61 top[x]=x; 62 } 63 if(son[x]) { 64 dfs2(son[x]); 65 } else { 66 leaf[++leaf[0]]=x; 67 } 68 for(unsigned i=0;i<e[x].size();i++) { 69 const int &y=e[x][i].to; 70 if(y==par[x]||y==son[x]) continue; 71 dfs2(y); 72 } 73 } 74 inline bool cmp(const int &x,const int &y) { 75 return dis[x]-dis[par[top[x]]]>dis[y]-dis[par[top[y]]]; 76 } 77 inline int query(const int &x,const int &y) { 78 if(rank[top[x]]<=y*2-1) { 79 return sum[std::min(y*2-1,leaf[0])]; 80 } 81 int u=x; 82 while(rank[top[u]]>y*2-1) { 83 u=par[top[u]]; 84 } 85 return sum[y*2-1]-std::min(std::min(sum[y*2-1]-sum[y*2-2],far[u]-dis[u]),dis[u])+(far[x]-dis[u]); 86 } 87 int main() { 88 const int n=getint(),q=getint(); 89 for(register int i=1;i<n;i++) { 90 const int u=getint(),v=getint(),w=getint(); 91 add_edge(u,v,w); 92 } 93 bfs(); 94 dfs1(root,0); 95 dfs2(root); 96 std::sort(&leaf[1],&leaf[1+leaf[0]],cmp); 97 for(register int i=1;i<=leaf[0];i++) { 98 rank[top[leaf[i]]]=i; 99 sum[i]=sum[i-1]+dis[leaf[i]]-dis[par[top[leaf[i]]]]; 100 } 101 for(register int i=0,ans=0;i<q;i++) { 102 const int x=(getint()+ans-1)%n+1,y=(getint()+ans-1)%n+1; 103 printf("%d ",ans=query(x,y)); 104 } 105 return 0; 106 }