题目：给出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
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int maxn = 250007; 4 typedef long long ll; 5 const int N=maxn; 6 struct data{ 7 int v;int nxt;ll val; 8 }edge[2*maxn]; 9 int dfu; 10 int dfin[N];//欧拉序入的时间戳 11 int dfou[N];//欧拉序列出的时间戳 12 int fa[22][N];//倍增用 13 ll mi[N];//i到1号点路径中最小的边权 14 int dep[N]; //深度 15 int lca(int u,int v){//倍增lca 16 if(dep[u]<dep[v])swap(u,v); 17 int del=dep[u]-dep[v]; 18 for(int i=0;del;del>>=1,i++){ 19 if(del&1){ 20 u=fa[i][u]; 21 } 22 }//到同一深度 23 if(u==v)return u; 24 for(int i=20;i>=0;i--){ 25 if(fa[i][u]!=fa[i][v]){u=fa[i][u],v=fa[i][v];} 26 } //从到lca的距离的二进制理解 即可立即为什么fa[0][v]就是是lca 27 return fa[0][v]; 28 } 29 int alist[maxn],cnt;int n; 30 31 void dfs(int x){ 32 dfin[x]=++dfu;//首位是入 出 时间戳 33 for(int i=1;fa[i-1][x];i++){//更新父节点信息 34 fa[i][x]=fa[i-1][fa[i-1][x]]; 35 } 36 int nxt=alist[x]; 37 while(nxt){//更新最小边权 38 int v=edge[nxt].v,val=edge[nxt].val; 39 if(dfin[v]==0){ 40 dep[v]=dep[x]+1; 41 mi[v]=min(mi[x],1ll*val); 42 fa[0][v]=x; 43 dfs(v); 44 } 45 nxt=edge[nxt].nxt; 46 } 47 dfou[x]=++dfu; 48 return ; 49 } 50 inline void add(int u,int v,ll val) 51 { edge[++cnt].v=v; 52 edge[cnt].nxt=alist[u]; 53 alist[u]=cnt; 54 edge[cnt].val=val; 55 } 56 bool cmp(int x,int y){//分为正负即可方便得判断是入 还是出 57 int k1=(x>0)?dfin[x]:dfou[-x]; 58 int k2=(y>0)?dfin[y]:dfou[-y]; 59 return k1<k2; 60 } 61 int tr[4*N]; 62 stack<int>s; 63 int m; 64 bool book[N]; 65 ll sum[N]; 66 67 int main(){ 68 scanf("%d",&n); 69 for(int i=1;i<=n-1;i++){ 70 int x,y,z; 71 scanf("%d%d%d",&x,&y,&z); 72 add(x,y,z);add(y,x,z); 73 } 74 mi[1]=0x3f3f3f3f; 75 dfs(1);//建立欧拉序 76 scanf("%d",&m); 77 for(int i=1;i<=m;i++){ 78 int tmp; 79 scanf("%d",&tmp); 80 for(int j=1;j<=tmp;j++){//把要求的点标记 81 scanf("%d",&tr[j]); 82 book[tr[j]]=1; 83 sum[tr[j]]=mi[tr[j]];//初始化删除重要点的sum[i]（sum指的是切断[i]的子树中所有重要点的最小代价 初始化为切掉该点即 从1--i的最小边权 意思是直接把这个子树切掉了） 84 } 85 sort(tr+1,tr+tmp+1,cmp);//对欧拉序列排序建立虚树 86 for(int j=1;j<tmp;j++){ 87 int lc=lca(tr[j],tr[j+1]); 88 if(!book[lc]){//树的建立 89 tr[++tmp]=lc; 90 book[lc]=1; 91 } 92 } 93 int nc=tmp; 94 for(int j=1;j<=nc;j++){//把每个点的负时间戳也加入 用负数表示这个的点现在是出去的点 95 tr[++tmp]=-tr[j]; 96 } 97 if(!book[1]){//强行把1号点加进来当根 98 tr[++tmp]=1;tr[++tmp]=-1; 99 } 100 sort(tr+1,tr+tmp+1,cmp);//重构欧拉序 101 for(int j=1;j<=tmp;j++){//模拟dfs 因为1--tmp是欧拉序列 所以可以直接用 102 if(tr[j]>0)s.push(tr[j]);//进栈 103 else { 104 int now=s.top();s.pop(); 105 if(now!=1){ 106 //状态转移方程sum[i]=sigma(min(mi[v],sum[v]) (v∈i.son) 107 int fa=s.top(); 108 sum[fa]+=min(sum[now],mi[now]); 109 } 110 else printf("%lld ",sum[1]); 111 sum[now]=0; 112 book[now]=false; 113 } 114 } 115 } 116 117 return 0; 118 }