题意:

给你一棵带边权的树,然后给出m次询问,每次询问一些点,问他们和点1不连通的最小代价…..

分析:

我们知道数据范围非常大,然后复杂度要么是O(n)要么是O(nlogn),我们考虑,我们怎么求最小代价,明显是一个dp可以解决的.但是每次直接O(n)dp一遍明显不行,我们考虑,询问的点的和最多和n同级,那么我们对于每次询问建出虚树,书上的边是两个点之间链上是最小值,然后在虚树上面dp就好了….

代码:



\#pragma GCC optimize(3) #include<bits/stdc++.h> #define LL long long const LL N=5e5+10; const LL inf=0x3f3f3f3f; const LL mod=1e9+7; using namespace std; template <typename tp> inline void read(tp &x) { x=0;char c=getchar();bool f=0; for(;c<'0'||c>'9';f=(c=='-'),c=getchar()); for(;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0',c=getchar()); if(f) x=-x; } int n,m; int head[N],cnt,ask[N],vis[N]; struct Edge{int next,to,cost;} edge[N*2]; void add(int from,int to,int cost) { edge[++cnt].next=head[from]; edge[cnt].to=to; edge[cnt].cost=cost; head[from]=cnt; } int dfn[N],num,fa[N][22],dep[N]; LL hua[N][22]; void dfs(int now,int fath,int cost) { dfn[now]=++num;fa[now][0]=fath; dep[now]=dep[fath]+1;hua[now][0]=cost; for(int i=1;i<=20;i++) fa[now][i]=fa[fa[now][i-1]][i-1]; for(int i=1;i<=20;i++) hua[now][i]=min(hua[fa[now][i-1]][i-1],hua[now][i-1]); for(int i=head[now];i;i=edge[i].next) { int to=edge[i].to; if(to==fath) continue; dfs(to,now,edge[i].cost); } } bool cmp(int a,int b){return dfn[a]<dfn[b];} int lca(int a,int b) { if(dep[a]<dep[b]) swap(a,b); for(int i=20;i>=0;i--) if(dep[fa[a][i]]>=dep[b]) a=fa[a][i]; if(a==b) return a; for(int i=20;i>=0;i--) if(fa[a][i]!=fa[b][i]) a=fa[a][i],b=fa[b][i]; return fa[a][0]; } stack<int> Vtree; vector<int> son[N]; LL coo(int a,int b,LL ret=inf) {for(int i=20;i>=0;i--) if(dep[fa[a][i]]>=dep[b]) ret=min(ret,hua[a][i]),a=fa[a][i];return ret;} LL dfs_ans(int now) { // if(vis[now]) return inf; LL ret=0,siz=son[now].size(); for(int i=0;i<siz;i++) ret+=min(dfs_ans(son[now][i]),coo(son[now][i],now)); son[now].clear(); if(vis[now]) return inf; return ret; } int main() { read(n); for(int i=1;i<n;i++) { int u,v,c; read(u),read(v),read(c); add(u,v,c),add(v,u,c); } dfs(1,1,inf); read(m); for(int cas=1,opt;cas<=m;cas++) { read(opt); for(int i=1;i<=opt;i++) read(ask[i]),vis[ask[i]]=1; sort(ask+1,ask+opt+1,cmp); Vtree.push(1); for(int i=1;i<=opt;i++) { int top=Vtree.top(),Lca=lca(top,ask[i]); while(dfn[top]>dfn[Lca]) { Vtree.pop(); if(Vtree.size()>=1&&dfn[Vtree.top()]>=dfn[Lca]) son[Vtree.top()].push_back(top); else { Vtree.push(Lca); son[Lca].push_back(top); } top=Vtree.top(); } Vtree.push(ask[i]); } while(!Vtree.empty()) { int top=Vtree.top(); Vtree.pop();if(Vtree.empty()) break; son[Vtree.top()].push_back(top); } printf("%lld\n",dfs_ans(1)); for(int i=1;i<=opt;i++) vis[ask[i]]=0; } return 0; }

Leave A Comment

发表评论

电子邮件地址不会被公开。 必填项已用*标注