刚学OI的萌新求助,WA30pts
查看原帖
刚学OI的萌新求助,WA30pts
137280
FC_Viiiiictor_K楼主2020/5/2 21:25
#define INL inline
#define REG register
#define M ((l+r)>>1)
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
INL ll read(){
	REG ll sum=0,sign=1;
	REG char tmp=getchar();
	while(tmp<'0'||tmp>'9'){
		if(tmp=='-'){
			sign=-1;
		}
		tmp=getchar();
	}
	while(tmp>='0'&&tmp<='9'){
		sum=(sum<<1)+(sum<<3)+tmp-'0';
		tmp=getchar();
	}
	return sum*sign;
}
const int maxn=5*114514;
struct edge{
	int f,t;
	ll len;
	INL edge(){
		f=t=len=-1;
	}
	INL edge(REG int _f,REG int _t,REG ll _len){
		f=_f;t=_t;len=_len;
	}
};
vector<edge> eds;
vector<int> graf[maxn];
int n,m;
int siz[maxn],fa[maxn],dep[maxn],cei[maxn],dfn[maxn];
ll shrt[maxn];
namespace cut{
	int cntr=1;
	int dfs1(int pos,int f,int ndep,ll nshrt){
		siz[pos]=1;
		fa[pos]=f;
		dep[pos]=ndep;
		shrt[pos]=nshrt;
		REG int maxi=-1;
		for(REG unsigned i=0;i<graf[pos].size();i++){
			REG edge e=eds[graf[pos][i]];
			if(e.t==f){
				continue;
			}
			siz[pos]+=dfs1(e.t,pos,ndep+1,min<ll>(e.len,nshrt));
			if(maxi==-1||siz[e.t]>siz[eds[graf[pos][maxi]].t]){
				maxi=i;
			}
		}
		if(maxi!=-1&&maxi){
			swap<int>(graf[pos][0],graf[pos][maxi]);
		}
		return siz[pos];
	}
	void dfs2(int pos,int ncei){
		cei[pos]=ncei;
		dfn[pos]=cntr++;
		if(eds[graf[pos][0]].t==fa[pos]){
			return;
		}
		dfs2(eds[graf[pos][0]].t,ncei);
		for(REG unsigned i=1;i<graf[pos].size();i++){
			REG edge e=eds[graf[pos][i]];
			if(e.t==fa[pos]){
				continue;
			}
			dfs2(e.t,e.t);
		}
	}
	INL int lca(REG int x,REG int y){
		while(cei[x]!=cei[y]){
			if(dep[cei[x]]>dep[cei[y]]){
				swap<int>(x,y);
			}
			y=fa[cei[y]];
		}
		return dep[x]>dep[y]?y:x;
	}
}
struct czakioi{
	int pos,id;
	INL czakioi(){
		pos=id=-1;
	}
	INL czakioi(REG int _pos,REG int _id){
		pos=_pos;id=_id;
	}
}lst[maxn];
INL bool cmp(czakioi p1,czakioi p2){
	return p1.id<p2.id;
}
int stak[maxn],frt;
bool flags[maxn];
ll dp[maxn];
vector<int> tre[maxn];
INL void insert(REG int x){
    if(!frt){
        stak[++frt]=x;
        return;
    }
    REG int anc=cut::lca(stak[frt],x);
    while(dep[anc]<dep[stak[frt-1]]){
        tre[stak[frt-1]].push_back(stak[frt]);
        frt--;
    }
    if(dep[anc]<dep[stak[frt]]){
        tre[anc].push_back(stak[frt--]);
    }
    if(stak[frt]!=anc){
        stak[++frt]=anc;
    }
    stak[++frt]=x;
}
void dfs3(int pos){
	dp[pos]=shrt[pos];
	if(flags[pos]){
		flags[pos]=0;
	}
	else{
		REG ll tmp=0;
		for(REG unsigned i=0;i<tre[pos].size();i++){
			REG int tar=tre[pos][i];
			dfs3(tar);
			tmp+=dp[tar];
		}
		dp[pos]=min<ll>(dp[pos],tmp);
	}
	tre[pos].clear();
}
int main(){
	n=read();
	for(REG int i=0;i<n-1;i++){
		REG int x=read(),y=read();
		REG ll l=read();
		eds.push_back(edge(x,y,l));
		eds.push_back(edge(y,x,l));
		graf[x].push_back(i<<1);
		graf[y].push_back(i<<1|1);
	}
	cut::dfs1(1,0,0,0x7FFFFFFFFFFFFFFF);
	cut::dfs2(1,1);
	m=read();
	for(REG int i=0;i<m;i++){
		REG int p=read();
		for(REG int j=0;j<p;j++){
			lst[j].pos=read();
			lst[j].id=dfn[lst[j].pos];
			flags[lst[j].pos]=1;
		}
		sort(lst,lst+p,cmp);
		if(lst->pos!=1){
			insert(1);
		}
		for(REG int j=0;j<p;j++){
			insert(lst[j].pos);
		}
		while(frt>1){
			tre[stak[frt-1]].push_back(stak[frt]);
			frt--;
		}
		frt=0;
		dfs3(1);
		printf("%lld\n",dp[1]);
	}
	return 0;
}

rt

2020/5/2 21:25
加载中...