希望更丰富的展现？使用Markdown
by wxy_god @ 2019-02-28 22:14:45
希望更丰富的展现？使用Markdown
by Le_temps_des_fleurs @ 2019-02-28 22:17:08
不希望更丰富的展现？不使用Markdown
by wxwoo @ 2019-02-28 22:23:37
```cpp
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
using namespace std;
struct EDGE {
long long to,v;
EDGE(long long too,long long vv) {
to=too,v=vv;
}
};
struct Node {
long long min,x;
Node(long long xx,long long minn) {
min=minn,x=xx;
}
};
const long long inf=1e9;
long long top,in[5000005],cnt,n,deep[5000005],minn[1000005][22],m;
int dfn[5000005], s[5000005],v[5000005],f[1000005][22];
vector<EDGE> g[5000005],g2[5000005];
long long cmp(long long x,long long y) {
return dfn[x]<dfn[y];
}
void dfs(long long x) {
cnt++,dfn[x]=cnt;
for(long long i=0; i<g[x].size(); i++) if(g[x][i].to!=f[x][0]) {
f[g[x][i].to][0]=x;
minn[g[x][i].to][0]=g[x][i].v;
deep[g[x][i].to]=deep[x]+1;
dfs(g[x][i].to);
}
}
Node lca(long long x,long long y) {
Node sb=Node(0,inf);
if(deep[x]<deep[y]) swap(x,y);
for(long long i=20; i>=0; i--) if(deep[f[x][i]]>=deep[y]) sb.min=min(sb.min,minn[x][i]),x=f[x][i];
if(x==y) {
sb.x=x;
return sb;
}
for(long long i=20; i>=0; i--) if(f[x][i]!=f[y][i]) sb.min=min(sb.min,min(minn[x][i],minn[y][i])),x=f[x][i],y=f[y][i];
sb.min=min(sb.min,min(minn[x][0],minn[y][0]));
sb.x=f[x][0];
return sb;
}
void add(long long x,long long y,long long v) {
if(x==y||!x||!y) return;
g2[x].push_back(EDGE(y,v));
g2[y].push_back(EDGE(x,v));
}
long long dfs2(long long x,long long fa) {
long long sum=0;
for(long long i=0; i<g2[x].size(); i++) if(g2[x][i].to!=fa) {
if(v[g2[x][i].to]) sum+=g2[x][i].v,dfs2(g2[x][i].to,x);
else sum+=min(g2[x][i].v,dfs2(g2[x][i].to,x));
}
g2[x].clear();
return sum==0?inf:sum;
}
int main() {
scanf("%lld",&n);
for(long long i=1; i<n; i++) {
long long x,y,z;
scanf("%lld%lld%lld",&x,&y,&z);
g[x].push_back(EDGE(y,z));
g[y].push_back(EDGE(x,z));
}
deep[1]=1;
dfs(1ll);
for(long long i=0; i<=20; i++) minn[0][i]=inf,minn[0][i]=inf;;
for(long long i=1; i<=n; i++) for(long long j=1; j<=20; j++) f[i][j]=f[f[i][j-1]][j-1],minn[i][j]=min(minn[i][j-1],minn[f[i][j-1]][j-1]);
scanf("%lld",&m);
while(m--) {
long long k;
scanf("%lld",&k);
for(long long i=1; i<=k; i++) scanf("%lld",&in[i]),v[in[i]]=1;
sort(in+1,in+1+k,cmp);
top=1,s[1]=1;
for(long long i=1; i<=k; i++) {
long long now=in[i],ff=lca(now,s[top]).x;
while(1) {
if(deep[ff]>=deep[s[top-1]]) {
add(ff,s[top],lca(ff,s[top]).min);
top--;
if(s[top]!=ff) top++,s[top]=ff;
break;
}
add(s[top-1],s[top],lca(s[top-1],s[top]).min);
top--;
}
if(s[top]!=now) top++,s[top]=now;
}
while(--top) add(s[top],s[top+1],lca(s[top],s[top+1]).min);
printf("%lld\n",dfs2(1ll,1ll));
for(long long i=1; i<=k; i++) v[in[i]]=0;
}
return 0;
}
```
by ieeqwq @ 2019-02-28 22:24:55
希望更丰富的展现？使用Markdown
by 刘心远 @ 2019-02-28 22:26:17