看别人的博客建虚树看了半天没看懂，按照自己的思路写，最后才发现是博主把一个深度depth写成了dfn 诶虚树入门，虚树建出来以后dp一下就出来了 虚树的构造主要思想就是维护右链 注意long long
#include <bits/stdc++.h>#define N 2000050#define LOG 25#define INF (1LL<<62)using namespace std;typedef long long LL;int rd() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f;}LL cut[N];int h[N],dfn[N],Jump[N][LOG+1],D[N],fa[N],tmp[N],cnt,tme;int sta[N],tp,k,tot,n,m;struct Edge{ int a,b,v,next; }e[2*N];inline void add(int a,int b,int v) { e[++cnt] = (Edge){a,b,v,h[a]};h[a] = cnt;}inline void add_Edge(int a,int b,int v) { add(a,b,v); add(b,a,v); }vector<int> E[N];inline void ins(int a,int b) { if (a == b) return ;// PRintf("::debug %d %d/n",a,b); E[a].push_back(b) , E[b].push_back(a); }void dfs(int u) { dfn[u] = ++tme; D[u] = D[ fa[u] ] + 1; for (int i=h[u];i;i=e[i].next) { int v = e[i].b , cp = e[i].v; if (dfn[v]) continue; cut[v] = min(cut[u] , 1LL*cp); Jump[v][0] = u; fa[v] = u , dfs(v); }}int LCA(int u,int v) { if (D[u] < D[v]) swap(u,v); for (int i=LOG;i>=0;i--) if (D[ Jump[u][i] ] >= D[v]) u = Jump[u][i]; if (u == v) return u; for (int i=LOG;i>=0;i--) if (Jump[u][i] != Jump[v][i]) u = Jump[u][i] , v = Jump[v][i]; return Jump[u][0];}bool cmp(int p1,int p2) { return dfn[p1] < dfn[p2]; }LL dp(int u,int fr) { LL ret = 0LL; for (int i=0;i<(int)E[u].size();i++) { int v = E[u][i]; if (v == fr) continue; ret += dp(v,u); } if (!ret) ret = cut[u]; E[u].clear(); return min(1LL*cut[u] , ret);}inline void solve() { #ifndef ONLINE_JUDGE memset(sta,0,sizeof(sta)); memset(tmp,0,sizeof(tmp)); #endif cnt = 0 , k = rd() , tot = 1; for (int i=1;i<=k;i++) tmp[i] = rd(); sort(tmp+1,tmp+k+1,cmp); for (int i=2;i<=k;i++) if (LCA(tmp[tot],tmp[i]) != tmp[tot]) tmp[++tot] = tmp[i]; sta[++tp] = 1; sta[++tp] = tmp[1]; for (int i=2;i<=tot;i++) { for (;;) { int now = tmp[i] , p = sta[tp] , q = sta[tp-1] , lca = LCA(now,p); if (D[q] > D[lca]) ins(q,p) , tp--; if (D[q] == D[lca]) { ins(lca,p); sta[tp--] = 0; break; } if (D[q] < D[lca]) { ins(lca,p); sta[tp] = lca; break; } } sta[++tp] = tmp[i]; } while (--tp) ins(sta[tp],sta[tp+1]); LL ans = dp(1,0); printf("%I64d/n",ans); return ;}void _pre() { for (int i=1;i<=LOG;i++) for (int _=1;_<=n;_++) Jump[_][i] = Jump[ Jump[_][i-1] ][i-1];}int main() { #ifndef ONLINE_JUDGE freopen("1.in","r",stdin); #endif n = rd(); for (int _=1;_<=n-1;_++) { int a=rd(),b=rd(),v=rd(); add_Edge(a,b,v); } cut[1] = INF; Jump[1][0] = 1; dfs(1); _pre(); m = rd(); for (int _=1;_<=m;_++) solve(); return 0;}新闻热点
疑难解答
