2 条题解
-
0
#include<bits/stdc++.h> using namespace std; typedef long long LL; const int N=1e6+10,inf=0x3f3f3f3f; vector<int>G[N],G2[N]; int n,k,a[N]; int tsp,dfn[N],dep[N],D,st[N][20]; void dfs(int x,int xfa) { dfn[x]=++tsp; dep[x]=dep[xfa]+1; st[x][0]=xfa;for(int i=1;i<=D;i++)st[x][i]=st[st[x][i-1]][i-1]; for(int y:G[x])if(y!=xfa)dfs(y,x); } int LCA(int x,int y) { if(dep[x]<dep[y])swap(x,y); for(int i=D;i>=0;i--)if(dep[st[x][i]]>=dep[y])x=st[x][i]; if(x==y)return x; for(int i=D;i>=0;i--)if(st[x][i]!=st[y][i])x=st[x][i],y=st[y][i]; return st[x][0]; } bool cmp(int x,int y){ return dfn[x]<dfn[y];} int sta[N],top; void build() { sort(a+1,a+k+1,cmp); sta[top=1]=1;if(a[1]!=1)sta[++top]=a[1]; for(int i=2;i<=k;i++) { int lca=LCA(sta[top],a[i]); while(top>1 && !(dep[sta[top-1]]<dep[lca]))G2[sta[top-1]].push_back(sta[top]),top--; if(lca!=sta[top])G2[lca].push_back(sta[top]),top--,sta[++top]=lca; sta[++top]=a[i]; } for(int i=1; i<top; i++)G2[sta[i]].push_back(sta[i+1]); } LL ans,mnn,mxx,mn[N],mx[N],g[N],siz[N];bool mk[N]; void DP(int x) { if(mk[x]) mx[x]=mn[x]=0; else mx[x]=-inf,mn[x]=inf; siz[x]=mk[x]; g[x]=0; for(int y:G2[x]) { DP(y); LL c=dep[y]-dep[x]; ans+=c*siz[x]*siz[y] + g[x]*siz[y] + g[y]*siz[x]; siz[x]+=siz[y]; g[x]+=g[y]+c*siz[y]; mnn=min(mnn,mn[x]+mn[y]+c); mxx=max(mxx,mx[x]+mx[y]+c); mn[x]=min(mn[x],mn[y]+c); mx[x]=max(mx[x],mx[y]+c); } G2[x].clear(); } int main() { scanf("%d",&n); for(int i=1,x,y;i<n;i++)scanf("%d%d",&x,&y),G[x].push_back(y),G[y].push_back(x); tsp=0;dep[0]=0;D=log2(n);dfs(1,0); int q;scanf("%d",&q); memset(mk,0,sizeof(mk)); while(q--) { scanf("%d",&k); for(int i=1;i<=k;i++)scanf("%d",&a[i]),mk[a[i]]=1; build(); ans=0,mnn=inf,mxx=-inf; DP(1); printf("%lld %lld %lld\n",ans,mnn,mxx); for(int i=1;i<=k;i++)mk[a[i]]=0; } return 0; } -
0
#include<bits/stdc++.h> using namespace std; typedef long long LL; const int N=1e6+10,inf=0x3f3f3f3f; vector<int>G[N],G2[N]; int n,k,a[N]; int tsp,dfn[N],dep[N],D,st[N][20]; void dfs(int x,int xfa) { dfn[x]=++tsp; dep[x]=dep[xfa]+1; st[x][0]=xfa;for(int i=1;i<=D;i++)st[x][i]=st[st[x][i-1]][i-1]; for(int y:G[x])if(y!=xfa)dfs(y,x); } int LCA(int x,int y) { if(dep[x]<dep[y])swap(x,y); for(int i=D;i>=0;i--)if(dep[st[x][i]]>=dep[y])x=st[x][i]; if(x==y)return x; for(int i=D;i>=0;i--)if(st[x][i]!=st[y][i])x=st[x][i],y=st[y][i]; return st[x][0]; } bool cmp(int x,int y){ return dfn[x]<dfn[y];} int sta[N],top; void build() { sort(a+1,a+k+1,cmp); sta[top=1]=1;if(a[1]!=1)sta[++top]=a[1]; for(int i=2;i<=k;i++) { int lca=LCA(sta[top],a[i]); while(top>1 && !(dep[sta[top-1]]<dep[lca]))G2[sta[top-1]].push_back(sta[top]),top--; if(lca!=sta[top])G2[lca].push_back(sta[top]),top--,sta[++top]=lca; sta[++top]=a[i]; } for(int i=1; i<top; i++)G2[sta[i]].push_back(sta[i+1]); } LL ans,mnn,mxx,mn[N],mx[N],g[N],siz[N];bool mk[N]; void DP(int x) { if(mk[x]) mx[x]=mn[x]=0; else mx[x]=-inf,mn[x]=inf; siz[x]=mk[x]; g[x]=0; for(int y:G2[x]) { DP(y); LL c=dep[y]-dep[x]; ans+=c*siz[x]*siz[y] + g[x]*siz[y] + g[y]*siz[x]; siz[x]+=siz[y]; g[x]+=g[y]+c*siz[y]; mnn=min(mnn,mn[x]+mn[y]+c); mxx=max(mxx,mx[x]+mx[y]+c); mn[x]=min(mn[x],mn[y]+c); mx[x]=max(mx[x],mx[y]+c); } G2[x].clear(); } int main() { scanf("%d",&n); for(int i=1,x,y;i<n;i++)scanf("%d%d",&x,&y),G[x].push_back(y),G[y].push_back(x); tsp=0;dep[0]=0;D=log2(n);dfs(1,0); int q;scanf("%d",&q); memset(mk,0,sizeof(mk)); while(q--) { scanf("%d",&k); for(int i=1;i<=k;i++)scanf("%d",&a[i]),mk[a[i]]=1; build(); ans=0,mnn=inf,mxx=-inf; DP(1); printf("%lld %lld %lld\n",ans,mnn,mxx); for(int i=1;i<=k;i++)mk[a[i]]=0; } return 0; }
- 1
信息
- ID
- 5276
- 时间
- 2000ms
- 内存
- 256MiB
- 难度
- 9
- 标签
- 递交数
- 291
- 已通过
- 32
- 上传者