本文主要是介绍虚数模板，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
fish学长 https://li-fish.github.io/2018/09/04/cjtk4cs8l008s04c2emfcercy/
给一颗树，根为1，边有边权。m次询问，每次询问给出k个关键点，割边使得根与任意关键点不连通，求最小花费。
#include <bits/stdc++.h>using namespace std;
typedef long long ll;
const int maxn = 250000+100;
struct node
{int v,nx;ll w;
}edge[2*maxn];int head[maxn],tot,top;
vector<int> q[maxn];
int n,nn;
ll val[maxn],dp[maxn];
int fa[maxn][26],dep[maxn],dfn[maxn];int vis[maxn];
vector<pair<int,int> > imp;
vector<int> G[maxn];
vector<int> occur;
int s[maxn],s_top;bool cmp(int a,int b)
{return dep[a] < dep[b];
}
void init()
{memset(head,-1,sizeof(head));tot = top = 0;val[1] = 1e18;
}
void add(int u,int v,ll w)
{edge[tot].v = v;edge[tot].w = w;edge[tot].nx = head[u];head[u] = tot++;
}
void dfs(int u,int f,int d)
{fa[u][0] = f,dep[u] = d,dfn[u] = ++top;for(int i = head[u];i != -1;i = edge[i].nx){int v = edge[i].v;if(v == f) continue;ll w = edge[i].w;val[v] = min(val[u],(ll)w);dfs(v,u,d+1);}
}
void init_LCA()
{dfs(1,-1,1);for(int i = 1;i <= 24;i++){for(int j = 1;j <= n;j++){fa[j][i] = fa[fa[j][i-1]][i-1];}}
}
//int get_pre(int u,int v) { //查询链上边权最小值
// int ans = 1e9;
// if(deep[u] < deep[v]) swap(u, v);
// int diff = deep[u] - deep[v];
// for(int i = 19; i >= 0; i--)
// if(diff>>i&1) {
// ans = min(ans,len[u][i]);
// u = fa[u][i];
// }
// if(u == v) return ans;
// for(int i = 19; i >= 0; i--)
// if(fa[u][i] != fa[v][i]) {
// ans = min(ans,len[u][i]);
// u = fa[u][i];
// ans = min(ans,len[v][i]);
// v = fa[v][i];
// }
// return min(ans,min(len[u][0],len[v][0]));
//}
//void lca_init(int n) {
// for(int j = 1; j <= 19; j++)
// for(int i = 1; i <= n; i++) {
// fa[i][j] = fa[fa[i][j-1]][j-1];
// len[i][j] = min(len[i][j-1],len[fa[i][j-1]][j-1]);
// }
}int LCA(int u,int v)
{if(dep[u] < dep[v]) swap(u,v);for(int i = 24;i >= 0;i--){if(dep[fa[u][i]] >= dep[v]){u = fa[u][i];}}if(u == v) return u;for(int i = 24;i >= 0;i--){if(fa[u][i] != fa[v][i]){u = fa[u][i],v = fa[v][i];}}return fa[u][0];
}
void build()
{sort(imp.begin(),imp.end());s[s_top = 1] = 1;occur.push_back(1);for(int i = 0;i < (int)imp.size();i++){int v = imp[i].second;int t = LCA(v,s[s_top]);occur.push_back(v);occur.push_back(t);while(dfn[t] < dfn[s[s_top]]){if(dfn[t] >= dfn[s[s_top-1]]){G[t].push_back(s[s_top]);if(s[--s_top] != t) s[++s_top] = t;break;}G[s[s_top-1]].push_back(s[s_top]);s_top--;}s[++s_top] = v;}while(s_top--) G[s[s_top]].push_back(s[s_top+1]);}
void dfs2(int x)
{if(vis[x]){dp[x] = val[x];return ;}ll sum =0;for(int i = 0;i < G[x].size();i++){int v = G[x][i];dfs2(v);sum += dp[v];
// cout<<dp[v]<<endl;}
// cout<<sum<<" "<<val[x]<<endl;dp[x] = min(sum,(ll)val[x]);
}
int main()
{scanf("%d",&n);init();for(int i = 1;i < n;i++){int u,v;ll w;scanf("%d%d%lld",&u,&v,&w);add(u,v,w);add(v,u,w);}init_LCA();int m;scanf("%d",&m);while(m--){int k;scanf("%d",&k);imp.clear();for(int i = 1;i <= k;i++){int t;scanf("%d",&t);vis[t] = 1;imp.push_back(make_pair(dfn[t],t));}build();dfs2(1);printf("%lld\n",dp[1]);for(int i = 0;i < occur.size();i++){G[occur[i]].clear();vis[occur[i]] = 0;}occur.clear();}return 0;
}
这篇关于虚数模板的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
