BZOJ2286: [Sdoi2011]消耗戰（虛樹）

---

BZOJ2286: [Sdoi2011]消耗戰

　　Time Limit: 20 Sec
　　Memory Limit: 512 MB

Description

　　在一場戰爭中，戰場由n個島嶼和n-1個橋梁組成，保證每兩個島嶼間有且僅有一條路徑可達。現在，我軍已經偵查到敵軍的總部在編號為1的島嶼，而且他們已經沒有足夠多的能源維系戰斗，我軍勝利在望。已知在其他k個島嶼上有豐富能源，為了防止敵軍獲取能源，我軍的任務是炸毀一些橋梁，使得敵軍不能到達任何能源豐富的島嶼。由于不同橋梁的材質和結構不同，所以炸毀不同的橋梁有不同的代價，我軍希望在滿足目標的同時使得總代價最小。
　　偵查部門還發現，敵軍有一臺神秘機器。即使我軍切斷所有能源之后，他們也可以用那臺機器。機器產生的效果不僅僅會修復所有我軍炸毀的橋梁，而且會重新隨機資源分布（但可以保證的是，資源不會分布到1號島嶼上）。不過偵查部門還發現了這臺機器只能夠使用m次，所以我們只需要把每次任務完成即可。
　

Input

　　第一行一個整數n，代表島嶼數量。
　　接下來n-1行，每行三個整數u,v,w，代表u號島嶼和v號島嶼由一條代價為c的橋梁直接相連，保證1<=u,v<=n且1<=c<=100000。
　　第n+1行，一個整數m，代表敵方機器能使用的次數。
　　接下來m行，每行一個整數ki，代表第i次后，有ki個島嶼資源豐富，接下來k個整數h1,h2,…hk，表示資源豐富島嶼的編號。
　

Output

　　輸出有m行，分別代表每次任務的最小代價。
　

Sample Input

　　10
　　1 5 13
　　1 9 6
　　2 1 19
　　2 4 8
　　2 3 91
　　5 6 8
　　7 5 4
　　7 8 31
　　10 7 9
　　3
　　2 10 6
　　4 5 7 8 3
　　3 9 4 6
　

Sample Output

　　12
　　32
　　22
　　　　

HINT

　　對于100%的數據，2<=n<=250000,m>=1,sigma(ki)<=500000,1<=ki<=n-1
　　

題目地址：　　BZOJ2286: [Sdoi2011]消耗戰

題目大意： 已經很簡潔了

題解：

　　裸的虛樹
　　
　　虛樹的概念
　　虛樹，就是在有一棵樹的情況下，對于數量較少的點進行詢問時所建的一棵新的樹，虛樹包含詢問的點和詢問的點的lca（最近公共祖先），上面的點被稱為關鍵點。對于兩個關鍵點A，B，它們的連邊上包含著原本樹上兩點之間那條鏈上的關鍵信息（這個信息可以是邊權最大值、邊權最小值、或者是邊權之和，這個取決于實際需要），然后就可以進行樹形dp了，這樣的復雜度是基于詢問的點數的，就可以想象虛樹就是把一棵大樹濃縮成一棵擁有所有你需要的信息的小樹。
　　
　　建樹的方法
那么怎么建樹呢，比較常見的做法是維護一個棧，里面存儲著一條鏈，每一次加入一個點進行操作。
具體列舉一下步驟吧
　　
　　預備知識：
　　用較優的復雜度求lca，以及求兩點之間的距離，一般倍增做，或者樹鏈剖分加前綴和都可以，這都是單次O（logn）的，另外呢，要事先求好原樹的dfs序和每個點的深度（這里的深度是指點序的深度，在計算這個深度的時候每條邊都是為1來算），后面要用
　　
　　詢問操作：
　　1.輸入每個詢問的點，并且按照dfs序為關鍵字排序
　　2.將第1個點壓到棧當中，開始構建虛樹
　　3.枚舉到下一個點u，計算u與棧頂點v的公共祖先lca
　　4.假設棧中棧頂下方的點為w（若棧中只有1個點就直跳過這一步），若w點的深度大于lca就把v向w連一條邊，并且彈掉v，重復此步，否則就到下一步
　　5.若lca不是當前的v，那么就把lca和v連邊，把v彈出，讓lca成為棧頂元素（注：這個操作的意思是如果棧頂沒有這個lca那么就壓入），否則不做任何操作
　　6.最后把u壓入棧中
　　7.回到3操作枚舉下個點，直到枚舉完了所有點
　　8.把棧頂v與棧頂下方的點為w連邊，并且把v彈掉，這么做直到棧里只有一個點
　　9.棧里剩下的點就是虛樹的根了
　　接下來你就可以開始進行dp等操作了
　　
　　虛樹的復雜度
　　虛樹的建樹的復雜度是O（k?log（n））的，樹形dp就是O（k）的啦，因為考慮最后虛樹上的關鍵點有詢問的點，和lca，然后每個詢問的點最多產生1個新的lca，所以復雜度就是對的啦
　　
　　來自https://blog.csdn.net/zhouyuheng2003/article/details/79110326
　　大神的博客里寫的很清楚了，具體看代碼實現吧：）
　　
　　此題很容易發現用 dp 解決
　　但是多組詢問 \(O(nm)\) 會TLE
　　重新建圖把點縮少再跑 dp 就好了
　　具體看代碼實現吧：）

---

AC代碼

#include <cstdio> 
#include <cstring>
#include <algorithm>
#define ll long long
using namespace std;
const int N=250005;
const ll inf=5e10;
int n,Q,K,top,ind;
int a[N],h[N];
int cnt,_cnt,last[N],_last[N];
inline int read(){int x=0;char ch=getchar();while(ch<'0'||ch>'9')ch=getchar();while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x;
}
struct edge{int to,val,next;
}e[N<<1];
struct _edge{int to,next;
}_e[N];
void add_edge(int u,int v,int w){e[++cnt]=(edge){v,w,last[u]};last[u]=cnt;e[++cnt]=(edge){u,w,last[v]};last[v]=cnt;
}
void _add_edge(int u,int v){if(u==v)return;_e[++_cnt]=(_edge){v,_last[u]};_last[u]=_cnt;
}
int pos[N],dep[N],fa[N][20];
ll mn[N];
void dfs(int u){pos[u]=++ind;for(int i=last[u];i;i=e[i].next){int v=e[i].to;if(v==fa[u][0])continue;fa[v][0]=u;dep[v]=dep[u]+1;mn[v]=min(mn[u],(ll)e[i].val);dfs(v);}
}
int lca(int a,int b){if(dep[a]<dep[b])swap(a,b);for(int i=18;i>=0;i--)if(dep[fa[a][i]]>=dep[b])a=fa[a][i];for(int i=18;i>=0;i--)if(fa[a][i]!=fa[b][i])a=fa[a][i],b=fa[b][i];if(a==b)return a;return fa[a][0];
}
bool cmp(int a,int b){return pos[a]<pos[b];
}
ll f[N];
void DP(int u){f[u]=mn[u];ll tmp=0;for(int i=_last[u];i;i=_e[i].next){int v=_e[i].to;DP(v);tmp+=f[v];}_last[u]=0;if(tmp!=0)f[u]=min(f[u],tmp);
}
int q[N];
void solve(){_cnt=0;K=read();for(int i=1;i<=K;i++)h[i]=read();sort(h+1,h+K+1,cmp);int tot=0;h[++tot]=h[1];for(int i=2;i<=K;i++)if(lca(h[tot],h[i])!=h[tot])h[++tot]=h[i];top=0;q[++top]=1;for(int i=1;i<=tot;i++){int now=h[i],F=lca(now,q[top]);while(1){if(dep[F]>=dep[q[top-1]]){_add_edge(F,q[top--]);if(q[top]!=F)q[++top]=F;break;}_add_edge(q[top-1],q[top]);top--;}if(q[top]!=now)q[++top]=now;}while(--top)_add_edge(q[top],q[top+1]);DP(1);printf("%lld\n",f[1]);
}
int main(){n=read();for(int i=1;i<n;i++){int u=read(),v=read(),w=read();add_edge(u,v,w);}mn[1]=inf;dep[1]=1;dfs(1);for(int j=1;j<=18;j++)for(int i=1;i<=n;i++)fa[i][j]=fa[fa[i][j-1]][j-1];Q=read();while(Q--)solve();return 0;
}

　　作者：skl_win
　　出處：https://www.cnblogs.com/shaokele/
　　本文版權歸作者和博客園共有，歡迎轉載，但未經作者同意必須保留此段聲明，且在文章頁面明顯位置給出原文連接，否則保留追究法律責任的權利。