数据范围是int,我检查了自己代码,没有类似前缀和或叠加之类的东西,甚至加法都见不到几个,但是答案却必须要用longlong,是怎么回事呢?(唯一可能爆int的地方我开了longlong但还是WA)
代码
#include<bits/stdc++.h>
using namespace std;
struct dino{int to,nxt,w;}e[501234];
struct vino{int to,nxt;}Ve[501234];
int n,m,Q,cnt,dcnt,a[251234],fst[251234],Vfst[251234];
int dep[251234],s[251234],dfn[251234],f[251234][22];
int sak[251234],top,u[251234],ufst[251234],t;
bool cmp(int p,int q){return dfn[p]<dfn[q];}
void edge(int sta,int edn,int w){
cnt++;
e[cnt]=(dino){edn,fst[sta],w};
fst[sta]=cnt;
}
void Vedge(int sta,int edn){
if(ufst[sta]!=t)Vfst[sta]=0,ufst[sta]=t;
cnt++;
Ve[cnt]=(vino){edn,Vfst[sta]};
Vfst[sta]=cnt;
}
void dfs(int o,int fa){
f[o][0]=fa;
for(int i=1;i<=20;i++)f[o][i]=f[ f[o][i-1] ][i-1];
dcnt++,dfn[o]=dcnt;
dep[o]=dep[fa]+1;
for(int E=fst[o];E;E=e[E].nxt){
int v=e[E].to;
if(v!=fa)s[v]=min(s[o],e[E].w),dfs(v,o);
}
}
int do_lca(int x,int y){
if(dep[x]<dep[y])swap(x,y);
for(int i=20;i>=0;i--){
if(dep[ f[x][i] ]<dep[y])continue;
x=f[x][i];
}
if(x==y)return x;
for(int i=20;i>=0;i--){
if(f[x][i]==f[y][i])continue;
x=f[x][i],y=f[y][i];
}
return f[x][0];
}
void buildV(int z){
if(top==1){top++,sak[top]=z;return ;}
int lca=do_lca(sak[top],z);
for("lyc";dfn[ sak[top-1] ]>=dfn[lca];top--){
if(top==1)break;
Vedge(sak[top-1],sak[top]);
Vedge(sak[top],sak[top-1]);
}
if(lca!=sak[top]){
Vedge(lca,sak[top]);
Vedge(sak[top],lca);
sak[top]=lca;
}
top++,sak[top]=z;
}
int DP(int o,int fa){
if(u[o]==t)return s[o];
long long nev_f=0;//用了加法,可能爆int
for(int E=Vfst[o];E;E=Ve[E].nxt){
int v=Ve[E].to;
if(v==fa)continue;
nev_f+=DP(v,o);
}
if(nev_f>s[o])nev_f=s[o];
return nev_f;
}
int main(){
scanf("%d",&n);
for(int i=1;i<n;i++){
int sta,edn,w;
scanf("%d%d%d",&sta,&edn,&w);
edge(sta,edn,w);
edge(edn,sta,w);
}
s[1]=INT_MAX;
dfs(1,0);
scanf("%d",&Q);
while(Q--){
t++;
scanf("%d",&m);
for(int i=1;i<=m;i++)scanf("%d",&a[i]),u[a[i]]=t;
sort(a+1,a+m+1,cmp);
top=1,sak[1]=1,cnt=0;
for(int i=1;i<=m;i++)buildV(a[i]);
for("lyc";top>0;top--){
Vedge(sak[top-1],sak[top]);
Vedge(sak[top],sak[top-1]);
}
long long ans=DP(1,0);//可能爆int
printf("%lld\n",ans);
}
}