我好像并没有写过虚树的题
然而我™为什么出过一道虚树题啊
那么作为虚树第一题还是讲一下虚树吧
虚树就是把所有的询问结点和他们两两的LCA取出新建一棵树,边权替换后再在上面进行dp等操作
具体实现可以将所有点按照dfs序排序,相邻的求LCA并加入,再去重,一定可以满足条件
连边的话就再按dfs序排序,建一个栈,每次不断将栈顶不为当前点的父辈的点弹出,直到是父辈节点,从栈顶向这个点连一条边,再将这个点丢进栈里即可
这题的dp还是比较简单的
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 |
// <2286.cpp> - 01/10/17 11:29:41 // This file is created by XuYike's black technology automatically. // Copyright (C) 2015 ChangJun High School, Inc. // I don't know what this program is. #include <iostream> #include <vector> #include <algorithm> #include <cstring> #include <cstdio> #include <cmath> using namespace std; typedef long long lol; int gi(){ int res=0,fh=1;char ch=getchar(); while((ch>'9'||ch<'0')&&ch!='-')ch=getchar(); if(ch=='-')fh=-1,ch=getchar(); while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar(); return fh*res; } const int MAXN=250010; const int MAXM=500010; const int K=20; const lol INF=1e17; int bt,b[MAXN],next[MAXM],to[MAXM],val[MAXM]; inline void add(int x,int y,int z){ next[++bt]=b[x];b[x]=bt;to[bt]=y;val[bt]=z; next[++bt]=b[y];b[y]=bt;to[bt]=x;val[bt]=z; } inline void add(int x,int y){next[++bt]=b[x];b[x]=bt;to[bt]=y;} int tot,dfn[MAXN],end[MAXN],f[K][MAXN],dep[MAXN]; lol v[MAXN]; void dfs(int x){ dfn[x]=++tot; for(int i=b[x];i;i=next[i]){ if(to[i]==f[0][x])continue; f[0][to[i]]=x; dep[to[i]]=dep[x]+1; v[to[i]]=min(v[x],lol(val[i])); dfs(to[i]); } end[x]=tot; } int cmp(int x,int y){return dfn[x]<dfn[y];} int lca(int x,int y){ if(dep[x]<dep[y])swap(x,y); int d=dep[x]-dep[y]; for(int i=0,p=1;i<K;i++,p<<=1) if(d&p)x=f[i][x]; if(x==y)return x; for(int i=K-1;i>=0;i--){ if(f[i][x]==f[i][y])continue; x=f[i][x];y=f[i][y]; } return f[0][x]; } int a[MAXN],s[MAXN]; bool y[MAXN]; lol dp(int x){ if(y[x])return v[x]; lol r=0; for(int i=b[x];i;i=next[i])r+=dp(to[i]); return min(r,v[x]); } int main(){ int n=gi(); for(int i=1;i<n;i++){ int u=gi(),v=gi(),w=gi(); add(u,v,w); } v[1]=INF;dfs(1); for(int j=1;j<K;j++) for(int i=1;i<=n;i++)f[j][i]=f[j-1][f[j-1][i]]; int m=gi(); while(m--){ int k=gi(),l=k; for(int i=1;i<=k;i++)y[a[i]=gi()]=1; sort(a+1,a+k+1,cmp); for(int i=1;i<l;i++)a[++k]=lca(a[i],a[i+1]);a[++k]=1; sort(a+1,a+k+1,cmp); k=unique(a+1,a+k+1)-a-1; int t=0;bt=0; for(int i=1;i<=k;i++){ b[a[i]]=0; while(t&&(dfn[a[i]]<dfn[s[t]]||end[s[t]]<dfn[a[i]]))t--; add(s[t],a[i]); s[++t]=a[i]; } printf("%lld\n",dp(1)); for(int i=1;i<=k;i++)y[a[i]]=0; } return 0; } |
泥天天刷火题!