网站营销推广有哪些,wordpress chm 下载,股权众筹网站开发,jquery效果网站对于每次询问#xff0c;构造出虚树#xff0c;相邻两点边权为该两点路径上边权的最小值 f[i]表示以i为根的子树与1不连通的最小代价,vip[i]表示i是不是关键点 f[i]sum(vip[j]?w[j]:min(f[j],w[j])) #includecstdio
#includealgorithm
#define N 250010
#de…对于每次询问构造出虚树相邻两点边权为该两点路径上边权的最小值 f[i]表示以i为根的子树与1不连通的最小代价,vip[i]表示i是不是关键点 f[i]sum(vip[j]?w[j]:min(f[j],w[j])) #includecstdio
#includealgorithm
#define N 250010
#define K 18
using namespace std;
typedef long long ll;
int n,Q,m,i,j,x,y,z,g[N],nxt[N1],v[N1],w[N1],ed,d[N],f[N][K],fm[N][K],st[N],en[N],dfn,a[N],q[N],t,tot;
bool vip[N],vis[N];
ll F[N];
inline bool cmp(int x,int y){return st[x]st[y];}
inline void read(inta){char c;while(!(((cgetchar())0)(c9)));ac-0;while(((cgetchar())0)(c9))(a*10)c-0;}
inline void add(int x,int y,int z){v[ed]y;w[ed]z;nxt[ed]g[x];g[x]ed;}
void dfs(int x){st[x]dfn;for(int i1;iK;i)f[x][i]f[f[x][i-1]][i-1],fm[x][i]min(fm[x][i-1],fm[f[x][i-1]][i-1]);for(int ig[x];i;inxt[i])if(v[i]!f[x][0])d[v[i]]d[f[v[i]][0]x]1,fm[v[i]][0]w[i],dfs(v[i]);en[x]dfn;
}
inline int lca(int x,int y){if(d[x]d[y])swap(x,y);for(int iK-1;~i;i--)if(d[f[x][i]]d[y])xf[x][i];if(xy)return x;for(int iK-1;~i;i--)if(f[x][i]!f[y][i])xf[x][i],yf[y][i];return f[x][0];
}
inline int ask(int x,int y){int tN;for(int iK-1;~i;i--)if(d[f[x][i]]d[y])tmin(t,fm[x][i]),xf[x][i];return t;
}
void dp(int x){F[x]0;for(int ig[x];i;inxt[i])dp(v[i]),F[x]vip[v[i]]?w[i]:min(F[v[i]],(ll)w[i]);
}
int main(){read(n);for(i1;in;i)read(x),read(y),read(z),add(x,y,z),add(y,x,z);for(i0;in;i)for(j0;jK;j)fm[i][j]N;dfs(d[1]1);for(i1;in;i)g[i]0;read(Q);while(Q--){read(m);vis[1]vip[1]a[1]1;for(totm,i2;im;i)read(a[i]),vis[a[i]]vip[a[i]]1;sort(a1,am1,cmp);for(i1;im;i)if(!vis[xlca(a[i],a[i1])])vis[a[tot]x]1;mtot,sort(a1,am1,cmp);for(ed0,q[t1]1,i2;im;q[t]a[i]){while(st[a[i]]st[q[t]]||en[a[i]]en[q[t]])t--;add(q[t],a[i],ask(a[i],q[t]));}for(dp(i1);im;i)vis[a[i]]vip[a[i]]g[a[i]]0;printf(%lld\n,F[1]);}return 0;
}转载于:https://www.cnblogs.com/clrs97/p/4403160.html
