Description

一棵 n 個結點的樹，有正邊權。
用 y 條鏈覆蓋這棵樹，滿足：

• 所有鏈連通（有重點即算作相連）
• 點 x 被覆蓋
• 被覆蓋的邊的權值和盡可能大
  q 次給出 x, y，詢問最大邊權和，強制在線。
  n, q ≤ $10^5$

Solution

• 可以發(fā)現一些比較顯然的性質：

權值是正的，那么鏈的端點一定可以全部調整成葉子。

如果鏈不連通，可以交換鏈的端點使它們連通。

使用 k 條路徑就可以覆蓋一棵有 2k 個葉子的樹。（先以任意方式匹配葉子。如果有兩條路徑不相交，可以調整成相交的情況。
不斷調整就可以讓任意兩條路徑都相交，于是顯然覆蓋了整棵樹。）

• 現在問題是尋找 2 ? y 個葉子，使 x 被包含，使被包含的邊權和最大。
• 考慮單次詢問怎么辦。如果只有一次詢問，我們就把詢問的點 x 提作根，如果 x 的度數不為 1 ，那么選 y 條路徑的最優(yōu)方案必然可以轉化為選 2y 個葉子，然后求這 2y 個葉子到 x 的路徑的并的長度。如果 x 的度數為 1 的話，那么就是選 2y-1 個葉子，因為有一條路徑要從 x 出發(fā)。
• 那么顯然就可以貪心的選當前貢獻最大的葉子加入答案了。
• 如果有多組詢問呢？每次詢問都換根顯然不現實，但發(fā)現每次詢問中，一定存在一種方案使得直徑的兩端中至少有一端被選取。
• 那我們就可以把直徑的兩個端點分別作為根來考慮，最后詢問的時候取最大值即可。
• 考慮對每棵樹預處理出 $an{s}_i$ 表示當前選了 i 個葉子的最大權值和，這個可以用 DFS序的線段樹或者是長鏈剖分來實現。

線段樹實現：每個葉子節(jié)點的貢獻是 它的深度-它到根路徑上已經被其它路徑覆蓋的部分的長度，用線段樹維護一下葉子的貢獻，每次貪心的選取貢獻最大的葉子

長鏈剖分實現：一個子樹內，最先被選的顯然是深度最大的葉子，那么一個葉子的貢獻，就是在長鏈剖分后，所在重鏈以及上方第一條輕邊的距離。

• 然后考慮一次詢問 x,y。如果 $an{s}_{2y?1}$中包含了 x 點，那么直接輸出 $an{s}_{2y?1}$即可。否則，加入 x 子樹內最深葉子，然后需要刪去一個之前選的葉子，使得減少的權值最小：

這個葉子可能是最后一個被選的葉子，也就是貢獻最小的那個。

由于 x 的加入，與 x 的 lca 最深的被選葉子的貢獻可能會減小，而被刪去。（找離 x 最近的有葉子被選的祖先的一條路徑，砍掉一半后跟 x 的子樹中深度最大的點接上。）

• 可以發(fā)現，第一種情況好辦，倍增跳到到第一個被訪問時間 $\le 2y?2$ 祖先 u ，那么答案就是 $an{s}_{2y?2}?dep[u]+mx[x]$。
• 然后考慮第二種情況。第二種情況乍一看需要維護在所有時間所有點的子樹內選的葉子節(jié)點的權值的最小值，這個很麻煩。但是仔細想想可以發(fā)現，只有在這個祖先的子樹內只有一個葉子節(jié)點被選的時候，這種情況才可能有第一種情況優(yōu)。因為如果多于兩個葉子，那么刪掉最小的那個葉子節(jié)點所減去的依舊是這個點加進來時候的權值，既然是減去加進來的權值那么第一種情況顯然是最小的。如果只有一個葉子，那么這個葉子所代表的鏈跟 x 到根的路徑是有交的，所以才有可能更短。實現方面可以倍增跳到第一個被訪問時間 $\le 2y?1$的節(jié)點 u，那么答案就會是 $an{s}_{2y?1}?mx[u]+mx[x]$。
• 那么最終的答案就是兩顆樹的兩種情況的最大值了。
• 時間復雜度 $O((n+q)\log n)$。
  疑問：就網上的其它博客和我自己的提交來看，直徑兩端點分別作為根的情況好像不用都考慮，隨便找一種就好。這樣做為什么是對的？知道的朋友可以麻煩解答一下嗎？

Code

#include<iostream> #include<cstdio> using namespace std; const int N=1e5+5; struct Edge{int v,w,nxt; }edge[N<<1]; int n,m,head[N],cnt,rt,mxd,lstans,ans[N]; int fa[N][25],dep[N],son[N],dfn[N],ind,ln[N],md[N],low[N]; pair<int,int> mx[N<<2];int tag[N<<2]; int vis[N]; void add(int u,int v,int w){edge[++cnt].v=v;edge[cnt].w=w;edge[cnt].nxt=head[u];head[u]=cnt; } void find(int u,int f,int d){if(d>mxd){rt=u;mxd=d;} for(int i=head[u];i;i=edge[i].nxt){int v=edge[i].v;if(v==f) continue;find(v,u,d+edge[i].w);} } void dfs(int u,int f){ln[dfn[u]=++ind]=u;md[u]=dep[u];for(int i=1;i<=20;i++){if(!fa[fa[u][i-1]][i-1]) break;fa[u][i]=fa[fa[u][i-1]][i-1];}for(int i=head[u];i;i=edge[i].nxt){int v=edge[i].v;if(v==f) continue;dep[v]=dep[u]+edge[i].w;fa[v][0]=u;dfs(v,u);md[u]=max(md[u],md[v]);}low[u]=ind; } void pushup(int u){if(mx[u<<1].first<mx[u<<1|1].first) mx[u]=mx[u<<1|1];else mx[u]=mx[u<<1]; } void build(int u,int l,int r){if(l==r){mx[u]=make_pair(dep[ln[l]],ln[l]);return;}int mid=(l+r)>>1;build(u<<1,l,mid);build(u<<1|1,mid+1,r);pushup(u); } void pushdown(int u,int l,int r){if(tag[u]){mx[u<<1].first+=tag[u];mx[u<<1|1].first+=tag[u];tag[u<<1]+=tag[u];tag[u<<1|1]+=tag[u];tag[u]=0;} } void update(int u,int l,int r,int a,int b,int w){if(a<=l&&r<=b){mx[u].first+=w;tag[u]+=w;return;}pushdown(u,l,r);int mid=(l+r)>>1;if(a<=mid) update(u<<1,l,mid,a,b,w);if(b>mid) update(u<<1|1,mid+1,r,a,b,w);pushup(u); } void prework(){dfs(rt,0);build(1,1,n);//貪心：每次選取貢獻最大的點,選完后修改其它點的貢獻 for(int i=2;i<=n;i++){ans[i]=ans[i-1]+mx[1].first;for(int j=mx[1].second;j&&!vis[j];j=fa[j][0]){vis[j]=i;update(1,1,n,dfn[j],low[j],dep[fa[j][0]]-dep[j]);}} } int solve(int x,int y){y=min(y,n);if(vis[x]<=y) return ans[y];//x已經被覆蓋int u=x;for(int i=20;i>=0;i--)if(vis[fa[x][i]]>y) x=fa[x][i];x=fa[x][0];return ans[y]+md[u]-dep[x]-min(dep[x],min(ans[y]-ans[y-1],md[x]-dep[x])); } int main(){scanf("%d%d",&n,&m);for(int i=1;i<n;i++){int u,v,w;scanf("%d%d%d",&u,&v,&w);add(u,v,w);add(v,u,w);}find(1,0,0);//找直徑端點 prework();for(int i=1;i<=m;i++){int u,v;scanf("%d%d",&u,&v);u=(u+lstans-1)%n+1;v=(v+lstans-1)%n+1;printf("%d\n",lstans=solve(u,v<<1));}return 0; }

參考文章：
https://www.luogu.com.cn/blog/46396/solution-cf526g

總結

以上是生活随笔為你收集整理的CF526G Spiders Evil Plan(树上最优性问题、倍增+线段树)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。