Description
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
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
32
22
HINT
对于100%的数据,2<=n<=250000,m>=1,sigma(ki)<=500000,1<=ki<=n-1
Solution
虚树真是个好东西啊QAQ
建议对虚树的理解看第一个,构建看第二个QAQ
题解去看第二个吧我也懒得写了XD
顺带提一句因为本题特殊,所以建虚树的时候要写成57行那样,否则就把57行删掉改成58行就行了。
至于本题为什么要像57行那么写呢……
假设$x$点是$y$的祖先,如果$x$到根不连通,那么$y$到根一定不连通,所以$y$点也就没有加进去的必要了。而且加进去的话像我这样$DP$也就不对了啊啊QAQQQQ
Code
1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 #include<algorithm> 5 #include<vector> 6 #define N (250009) 7 #define LL long long 8 using namespace std; 9 10 struct Edge{ int to,next,len;}edge[N<<1]; 11 int n,m,k,u,v,l,dfs_num; 12 int a[N],Depth[N],f[N][19],DFN[N]; 13 LL Min[N]; 14 int head[N],num_edge; 15 16 void add(int u,int v,int l) 17 { 18 edge[++num_edge].to=v; 19 edge[num_edge].next=head[u]; 20 edge[num_edge].len=l; 21 head[u]=num_edge; 22 } 23 24 void DFS(int x,int fa) 25 { 26 f[x][0]=fa; 27 for (int i=1; i<=18; ++i) f[x][i]=f[f[x][i-1]][i-1]; 28 DFN[x]=++dfs_num; Depth[x]=Depth[fa]+1; 29 for (int i=head[x]; i; i=edge[i].next) 30 if (edge[i].to!=fa) 31 { 32 Min[edge[i].to]=min(Min[x],(LL)edge[i].len); 33 DFS(edge[i].to,x); 34 } 35 } 36 37 int LCA(int x,int y) 38 { 39 if (Depth[x]<Depth[y]) swap(x,y); 40 for (int i=18; i>=0; --i) 41 if (Depth[f[x][i]]>=Depth[y]) x=f[x][i]; 42 if (x==y) return x; 43 for (int i=18; i>=0; --i) 44 if (f[x][i]!=f[y][i]) x=f[x][i], y=f[y][i]; 45 return f[x][0]; 46 } 47 48 vector<int>E[N]; 49 void ADD(int x,int y) {E[x].push_back(y);} 50 int stack[N],top; 51 bool cmp(int x,int y) { return DFN[x]<DFN[y];} 52 53 void Insert(int x) 54 { 55 if (top==1) {stack[++top]=x; return;} 56 int lca=LCA(x,stack[top]); 57 if (lca==stack[top]) return; 58 // if (lca==stack[top]) {stack[++top]=x; return;} 59 while (top>1 && DFN[stack[top-1]]>=DFN[lca]) 60 ADD(stack[top-1],stack[top]), top--; 61 if (lca!=stack[top]) ADD(lca,stack[top]), stack[top]=lca; 62 stack[++top]=x; 63 } 64 65 void Build() 66 { 67 stack[top=1]=1; 68 for (int i=1; i<=k; ++i) Insert(a[i]); 69 while (top>=2) ADD(stack[top-1],stack[top]), top--; 70 } 71 72 LL DP(int x) 73 { 74 int sz=E[x].size(); 75 if (!sz) return Min[x]; 76 LL ans=0; 77 for (int i=0; i<sz; ++i) 78 ans+=DP(E[x][i]); 79 E[x].clear(); 80 return min(ans,Min[x]); 81 } 82 83 int main() 84 { 85 Min[1]=1e18; 86 scanf("%d",&n); 87 for (int i=1; i<=n-1; ++i) 88 { 89 scanf("%d%d%d",&u,&v,&l); 90 add(u,v,l); add(v,u,l); 91 } 92 DFS(1,0); 93 scanf("%d",&m); 94 for (int i=1; i<=m; ++i) 95 { 96 scanf("%d",&k); 97 for (int j=1; j<=k; ++j) scanf("%d",&a[j]); 98 sort(a+1,a+k+1,cmp); 99 Build(); 100 printf("%lld\n",DP(1)); 101 } 102 }
转载于:https://www.cnblogs.com/refun/p/10064045.html
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/101285.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...