90ptsWA on #6 对拍了1w+组无果 码风良好 求调

#include<iostream>
#include<vector>
#include<algorithm>
#define int long long
using namespace std;
int read(){
    int k=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')k=k*10+c-'0',c=getchar();
    return k*f;
}
const int N=5e6+50,inf=1e18;
vector< pair<int,int> >g[N];
int n,m,cost[N],dfn[N];
bool iskey[N];
namespace sep{
	int fa[N],dep[N],siz[N],top[N],son[N],rkn[N],idx;
	void dfs1(int u,int f){
		fa[u]=f,dep[u]=dep[f]+1,siz[u]=1;
		for(auto v:g[u]){
			if(v.first==f){
				cost[u]=min(cost[f],v.second);
				continue;
			}
			dfs1(v.first,u);
			siz[u]+=siz[v.first];
			if(siz[v.first]>siz[son[u]])son[u]=v.first;
		}
	} 
	void dfs2(int u,int ftop){
		top[u]=ftop,dfn[u]=++idx,rkn[idx]=u;
		if(son[u]==0)return;
		dfs2(son[u],ftop);
		for(auto v:g[u]){
			if(v.first!=son[u]&&v.first!=fa[u]){
				dfs2(v.first,v.first);
			}
		}
	}
	int lca(int u,int v){
		while(top[u]!=top[v]){
			if(dep[top[u]]<dep[top[v]])swap(u,v);
			u=fa[top[u]];
		}
		return (dep[u]<dep[v])?u:v;
	}
}
bool cmp(int x,int y){
	return dfn[x]<dfn[y];
}
vector<int>h[N];
int sta[N],len,k,key[N];
int f[N];
void print(int x){
	cout<<x<<':';
	for(auto v:h[x]){
		cout<<v<<' ';
	}
	cout<<endl;
	for(auto v:h[x]){
		print(v);
	}
}
void build(){
	for(int i=1;i<=k;i++){
		iskey[key[i]]=false;
	}
	k=read();
	for(int i=1;i<=k;i++){
		key[i]=read();
		iskey[key[i]]=true;
	}
	//init
	len=0,sta[++len]=1;h[1].clear();
	sort(key+1,key+1+k,cmp);
	for(int i=1;i<=k;i++){
		int l=sep::lca(sta[len],key[i]);
		if(l!=sta[len]){
			while(dfn[l]<dfn[sta[len-1]]){
				h[sta[len-1]].push_back(sta[len]),len--; 
			}
			if(dfn[l]>dfn[sta[len-1]]){ 
				h[l].clear();//第一次入栈，清空 
				h[l].push_back(sta[len]);//连边 
				sta[len]=l;//弹栈顶并将LCA入栈 
			}else{//此时l=sta[len-1] 
				h[l].push_back(sta[len]);//连边
				len--; 
			}
		}
		sta[++len]=key[i];
		h[key[i]].clear();
	}
	for(int i=1;i<len;i++){
		h[sta[i]].push_back(sta[i+1]);
	}
}
int dp(int u){
	if(iskey[u])return f[u]=cost[u];
	int tot=0;
	for(auto v:h[u]){
		tot+=dp(v);
	}
	return f[u]=min(cost[u],tot);
}
signed main(){
	n=read();
	for(int i=1;i<=n-1;i++){
		int u=read(),v=read(),w=read();
		g[u].push_back(make_pair(v,w));
		g[v].push_back(make_pair(u,w));
	}
	cost[1]=inf;
	sep::dfs1(1,0);
	sep::dfs2(1,1); 
	m=read();
	for(int i=1;i<=m;i++){
		build();
		printf("%lld\n",dp(1));
	}
	return 0;
}

#include<iostream>
#include<time.h>
#include<vector>
#include<string.h>
using namespace std;
int rd(int l,int r){
	return l+rand()%(r-l+1);
}
int idx=1;
int main(){
	srand(time(NULL));
	int n=10000,m=10;
	cout<<n<<endl;
	for(int i=1;i<=n-1;i++){
		cout<<rd(1,idx)<<' '<<idx+1<<' '<<rd(1,1e5)<<endl;
		idx++;
	}
	cout<<m<<endl;
	for(int i=1;i<=m;i++){
		int k=rd(1,n-1);
		cout<<k<<' ';
		vector<int>arr(n+1);
		for(int i=1;i<=n;i++)arr[i]=i;
		for(int i=1;i<=n;i++)swap(arr[rd(1,n)],arr[rd(1,n)]);
		for(int i=1;i<=k;i++){
			if(arr[i]!=1)cout<<arr[i]<<' ';
			else k++;
		}
		cout<<endl;
	}
	return 0; 
}

#include <bits/stdc++.h>
#define INL inline
#define REG register
#define DB double
#define LDB long double
#define ULL unsigned long long
#define LL long long

#define RPT(i,x,y) for (REG int i=x;i<y;i++)
#define DRPT(i,x,y) for (REG int i=x;i>y;i--)
#define MST(a,b) memset(a,b,sizeof(a))

#define MAXN 500500
#define MAXM 10000
#define MOD 998244353
#define INF 0x3f3f3f3f
#define LLINF 0x3f3f3f3f3f3f3f3f 
#define EPS 1e-5

#define _ 0
using namespace std;

int dfn[MAXN];
int dep[MAXN];
int fa[MAXN][25];
LL minv[MAXN];
int m[MAXN];
int lst[MAXN];
bool query[MAXN];
int n,q;
int num;
int top;
int dfscnt=1;

int stak[MAXN];

struct EDGE
{
	int to,next;
	LL val;
}edge[MAXN<<1],edge1[MAXN<<1]; 

int head[MAXN];//初始图存储 
int cnt=1;
INL void add(int x,int y,LL v)
{
	edge[cnt].next=head[x];
	edge[cnt].to=y;
	edge[cnt].val=v;
	head[x]=cnt++;
}

int head1[MAXN];//虚树存储 
int cnt1=1;
INL void add1(int x,int y)
{
	edge1[cnt1].next=head1[x];
	edge1[cnt1].to=y;
	head1[x]=cnt1++;
}

void dfs(int pos)
{
	int k;
	for (k=0;fa[pos][k];k++)
		fa[pos][k+1]=fa[fa[pos][k]][k];
	m[pos]=k;
	dfn[pos]=dfscnt++;
	for (int i=head[pos];i;i=edge[i].next)
	{
		REG int to=edge[i].to;
		if (!dfn[to])
		{
			dep[to]=dep[pos]+1;
			minv[to]=min(minv[pos],edge[i].val);
			fa[to][0]=pos;
			dfs(to);
		}
	}
}

LL dfs1(int pos) //dp
{
	LL sum=0;
	LL tem;
	for (int i=head1[pos];i;i=edge1[i].next)
	{
		int to=edge1[i].to;
		sum+=dfs1(to);
	}
	if (query[pos])
		tem=minv[pos];
	else
		tem=min(minv[pos],sum);
	query[pos]=false; //清空虚树 
	head1[pos]=0;
	return tem;
}

int lca(int x,int y) //倍增LCA 
{
	if (dep[x]<dep[y])
		swap(x,y);
	DRPT(i,m[x],-1)
		if (dep[fa[x][i]]>=dep[y])
			x=fa[x][i];
	if (x==y)
		return x;
	DRPT(i,m[x],-1)
		if (fa[x][i]!=fa[y][i])
		{
			x=fa[x][i];
			y=fa[y][i];
		}
	return fa[x][0];
} 

bool cmp(int x1,int x2)
{
	return dfn[x1]<dfn[x2];
}

int main()
{
	minv[1]=LLINF;
	cin>>n;
	int x,y;
	LL v;
	RPT(i,0,n-1)
	{
		scanf("%d%d%lld",&x,&y,&v);
		add(x,y,v);
		add(y,x,v);
	}
	dfs(1);
	cin>>q;
	while (q--)
	{
		cin>>num;
		RPT(i,1,num+1)
		{
			scanf("%d",&lst[i]);
			query[lst[i]]=true;
		}
		sort(lst+1,lst+num+1,cmp);
		stak[top=1]=lst[1];
		RPT(i,2,num+1)
		{
			int now=lst[i];
			int lc=lca(now,stak[top]);
			while (1)
				if (dep[lc]>=dep[stak[top-1]])
				{
					if (lc!=stak[top]) //不满足该条件为情况一 
					{
						add1(lc,stak[top]);
						if (lc!=stak[top-1]) //情况二 
							stak[top]=lc;
						else //情况三 
							top--;
					}
					break;
				}
				else //情况四
				{
					add1(stak[top-1],stak[top]);  
					top--;
				}
			stak[++top]=now; //最后统一把now压进栈中 
		}
		while (--top)
			add1(stak[top],stak[top+1]); //将最右链放进虚树 
		cout<<dfs1(stak[1])<<endl;
		cnt1=1;
	}
	return ~~(0^_^0);
}

#include<iostream>
using namespace std;
int main(){
	for(int i=1;i<=10000;i++){
		cout<<"#"<<i<<'\n';
		system("make.exe>in.txt");
		system("run.exe<in.txt>r.txt");
		system("tj.exe<in.txt>t.txt");
		if(system("fc r.txt t.txt")){
			return 0;
		}
	}
	return 0;
}