#7 RE 求助
查看原帖
#7 RE 求助
299655
nagisa_kun楼主2020/6/5 00:29
#include <iostream>
#include <map>
#include <ctime>
#include <vector>
#include <climits>
#include <algorithm>
#include <random>
#include <cstring>
#include <cstdio>
#include <map>
#include <set>
#include <bitset> 
#include <queue>
#define inf 0x3f3f3f3f
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);
#define rep(i, a, n) for( int i = a; i <= n; ++ i)
#define per(i, a, n) for( int i = n; i >= a; -- i)
#define ONLINE_JUDGE
using namespace std;
typedef long long ll;
template<typename T>void write(T x)
{
    if(x<0)
    {
        putchar('-');
        x=-x;
    }
    if(x>9)
    {
        write(x/10);
    }
    putchar(x%10+'0');
}
 
template<typename T> void read(T &x)
{
    x = 0;char ch = getchar();ll f = 1;
    while(!isdigit(ch)){if(ch == '-')f*=-1;ch=getchar();}
    while(isdigit(ch)){x = x*10+ch-48;ch=getchar();}x*=f;
}
//==============================================================
const int maxn=250005+1000;
struct Edge{
    int next,to;
    int w;
}e[maxn<<1];
struct Edgev{
    int next,to;
}ev[maxn];
int n;
int k;
ll head[maxn],cnt;
ll par[maxn][30],depth[maxn];
ll tmp[maxn];
ll lg[30],m;
ll st[maxn<<1],top;//
ll dfn[maxn<<1],tim;
ll headv[maxn],cntv;//
ll nm[maxn];
int lca(int a,int b){
	if(depth[a]<depth[b]) swap(a,b);
	while(depth[a]>depth[b]) a = par[a][lg[depth[a]-depth[b]]-1];
	if(a==b) return a;
	for(int i=lg[depth[a]]-1;i>=0;i--){
		if(par[a][i]!=par[b][i]){
			a=par[a][i];
			b=par[b][i];
		}
	}
	return par[a][0];
}
void add(int x,int y,int w){
    e[cnt].to=y;
    e[cnt].w=w;
    e[cnt].next=head[x];
    head[x]=cnt++;
}
void addv(int x,int y){
    ev[cntv].to=y;
    ev[cntv].next=headv[x];
    headv[x]=cntv++;
}
void dfs(ll u,ll fa,ll de){
	depth[u]=de;
	par[u][0]=fa;
    dfn[u]=++tim;
	for(int i=1;i<=lg[depth[u]];i++){
		par[u][i]=par[par[u][i-1]][i-1];
	}
	for(int i=head[u];~i;i=e[i].next){
		int v=e[i].to;
		if(v==fa) continue;
        nm[v]=min(nm[u],(ll)e[i].w);
		dfs(v,u,de+1);
	}
}
bool cmp(int a,int b){
    return dfn[a]<dfn[b];
}
void insert(int x) {
    if(top == 1) {st[++top] = x; return ;}
    int LCA = lca(x, st[top]);
    if(LCA == st[top]) return ;
    while(top > 1 && dfn[st[top - 1]] >= dfn[LCA]) addv(st[top - 1], st[top]), top--;
    if(LCA != st[top]) addv(LCA, st[top]), st[top] = LCA;//
    st[++top] = x;
}

ll dp(int x) {
    int flag=0;
    ll sum=0;
    for(int i=headv[x];~i;i=ev[i].next){
        int v=ev[i].to;
        flag=1;
        sum+=dp(v);
    }
    headv[x]=-1;
    if(flag==0) return nm[x];
    return min(nm[x],sum);
}

int main()
{
    #ifndef ONLINE_JUDGE
	freopen("in.txt","r",stdin);
	freopen("out.txt","w",stdout);
	#endif
	//clock_t c1 = clock();
	//===========================================================
    nm[1]=INT64_MAX;
    rep(i,1,30-1){
        lg[i]=lg[i-1]+((1<<lg[i-1])==i);
    }
    read(n);
    memset(head,-1,sizeof(head));
    memset(headv,-1,sizeof(headv));
    rep(i,1,n-1){
        int a,b;
        ll c;
        scanf("%d %d %lld",&a,&b,&c);
        add(a,b,c),add(b,a,c);
    }
    dfs(1,0,0);
    scanf("%d",&m);
    while(m--){
        top=1;
        st[top]=1;
        cntv=0;
        read(k);
        rep(i,1,k){
            scanf("%d",tmp+i);
        }
        sort(tmp+1,tmp+1+k,[](int a,int b){
            return dfn[a]<dfn[b];
        });
        rep(i,1,k) insert(tmp[i]);
        while(top>0)addv(st[top-1],st[top]),top--;
        ll ans=dp(1);
        printf("%lld",ans),putchar('\n');
    }
	//===========================================================
	//std::cerr << "Time:" << clock() - c1 << "ms" << std::endl;
	return 0;
}
2020/6/5 00:29
加载中...