题目: 给出 n 个点的树 q 次询问 问切断 k 个点 (不和 1 号点联通) 的最小代价是多少
思路: 树形 dp sum[i]表示切断 i 的子树中需要切断的点的最小代价是多少 mi[i]表示 1--i 中的最小边权
sum[i]=min(mi[i],sigma(min(mi[v],sum[v]) (v∈i.son))
从根向上 dp 这里巧妙运用了欧拉序(每个点入和出的按时间顺序排列的序列)
题目链接: https://www.luogu.org/problemnew/show/P2495
参考: https://www.luogu.org/problemnew/solution/P2495
- #include<bits/stdc++.h>
- using namespace std;
- const int maxn = 250007;
- typedef long long ll;
- const int N=maxn;
- struct data{
- int v;int nxt;ll val;
- }edge[2*maxn];
- int dfu;
- int dfin[N];// 欧拉序入的时间戳
- int dfou[N];// 欧拉序列出的时间戳
- int fa[22][N];// 倍增用
- ll mi[N];//i 到 1 号点路径中最小的边权
- int dep[N]; // 深度
- int lca(int u,int v){// 倍增 lca
- if(dep[u]<dep[v])swap(u,v);
- int del=dep[u]-dep[v];
- for(int i=0;del;del>>=1,i++){
- if(del&1){
- u=fa[i][u];
- }
- }// 到同一深度
- if(u==v)return u;
- for(int i=20;i>=0;i--){
- if(fa[i][u]!=fa[i][v]){u=fa[i][u],v=fa[i][v];}
- } // 从到 lca 的距离的二进制理解 即可立即为什么 fa[0][v]就是是 lca
- return fa[0][v];
- }
- int alist[maxn],cnt;int n;
- void dfs(int x){
- dfin[x]=++dfu;// 首位是入 出 时间戳
- for(int i=1;fa[i-1][x];i++){// 更新父节点信息
- fa[i][x]=fa[i-1][fa[i-1][x]];
- }
- int nxt=alist[x];
- while(nxt){// 更新最小边权
- int v=edge[nxt].v,val=edge[nxt].val;
- if(dfin[v]==0){
- dep[v]=dep[x]+1;
- mi[v]=min(mi[x],1ll*val);
- fa[0][v]=x;
- dfs(v);
- }
- nxt=edge[nxt].nxt;
- }
- dfou[x]=++dfu;
- return ;
- }
- inline void add(int u,int v,ll val)
- { edge[++cnt].v=v;
- edge[cnt].nxt=alist[u];
- alist[u]=cnt;
- edge[cnt].val=val;
- }
- bool cmp(int x,int y){// 分为正负即可方便得判断是入 还是出
- int k1=(x>0)?dfin[x]:dfou[-x];
- int k2=(y>0)?dfin[y]:dfou[-y];
- return k1<k2;
- }
- int tr[4*N];
- stack<int>s;
- int m;
- bool book[N];
- ll sum[N];
- int main(){
- scanf("%d",&n);
- for(int i=1;i<=n-1;i++){
- int x,y,z;
- scanf("%d%d%d",&x,&y,&z);
- add(x,y,z);add(y,x,z);
- }
- mi[1]=0x3f3f3f3f;
- dfs(1);// 建立欧拉序
- scanf("%d",&m);
- for(int i=1;i<=m;i++){
- int tmp;
- scanf("%d",&tmp);
- for(int j=1;j<=tmp;j++){// 把要求的点标记
- scanf("%d",&tr[j]);
- book[tr[j]]=1;
- sum[tr[j]]=mi[tr[j]];// 初始化删除重要点的 sum[i](sum 指的是切断 [i] 的子树中所有重要点的最小代价 初始化为切掉该点即 从 1--i 的最小边权 意思是直接把这个子树切掉了)
- }
- sort(tr+1,tr+tmp+1,cmp);// 对欧拉序列排序建立虚树
- for(int j=1;j<tmp;j++){
- int lc=lca(tr[j],tr[j+1]);
- if(!book[lc]){// 树的建立
- tr[++tmp]=lc;
- book[lc]=1;
- }
- }
- int nc=tmp;
- for(int j=1;j<=nc;j++){// 把每个点的负时间戳也加入 用负数表示这个的点现在是出去的点
- tr[++tmp]=-tr[j];
- }
- if(!book[1]){// 强行把 1 号点加进来当根
- tr[++tmp]=1;tr[++tmp]=-1;
- }
- sort(tr+1,tr+tmp+1,cmp);// 重构欧拉序
- for(int j=1;j<=tmp;j++){// 模拟 dfs 因为 1--tmp 是欧拉序列 所以可以直接用
- if(tr[j]>0)s.push(tr[j]);// 进栈
- else {
- int now=s.top();s.pop();
- if(now!=1){
- // 状态转移方程 sum[i]=sigma(min(mi[v],sum[v]) (v∈i.son)
- int fa=s.top();
- sum[fa]+=min(sum[now],mi[now]);
- }
- else printf("%lld\n",sum[1]);
- sum[now]=0;
- book[now]=false;
- }
- }
- }
- return 0;
- }
- View Code
P2495 [SDOI2011]消耗战 lca 倍增 + 虚树 + 树形 dp
来源: http://www.bubuko.com/infodetail-3006596.html