「题意」给你一棵树,每次询问若在在选中的k个点两两连接无相边,边权为原来树上的点对距离,求这些边的:1)权值和 2)最短的边 3)最长的边。所有k之和$le$2*n。
「分析」虚树模板题。(但是独立写出来还是很振奋人心的合)直接考虑对虚树dp,设pmn[x]为x到x的子树内的关键点的最短距离,pmx[x]为最长距离,sum[x]为x到子树内所有关键点的距离之和。这些都很好处理。统计答案利用树形dp的常用技巧——有当前子树和以前的子树进行组合。
「实现」
/* 写对啦!woc */ #include <bits/stdc++.h> #define ll long long using namespace std; const int n=1e6+10; const int inf=0x3f3f3f3f; int n,q,k; int dfn[n],dep[n],fa[n][20]; vector<int> e[n]; void pre(int x,int pa) { static int cnt=0; dfn[x]=++cnt; dep[x]=dep[fa[x][0]=pa]+1; for(int i=1; (1<<i)<=dep[x]; ++i) fa[x][i]=fa[fa[x][i-1]][i-1]; for(unsigned i=0; i<e[x].size(); ++i) if(e[x][i]!=pa) pre(e[x][i],x); } int lca(int x,int y) { if(dep[x]<dep[y]) swap(x,y); int dif=dep[x]-dep[y]; for(int i=19; ~i; --i) if(dif&(1<<i)) x=fa[x][i]; if(x==y) return x; for(int i=19; ~i; --i) if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i]; return fa[x][0]; } int a[n],s[n],top,cnt; int head[n],to[n<<1],len[n<<1],last[n<<1]; void add_edge(int x,int y,int w) { to[++cnt]=y; len[cnt]=w; last[cnt]=head[x]; head[x]=cnt; } bool cmp(int x,int y) { return dfn[x]<dfn[y]; } void ist(int x) { if(top==1) { if(x!=1) s[++top]=x; return; } int t=lca(s[top],x); if(t!=s[top]) { for(; top>1&&dfn[s[top-1]]>=dfn[t]; top--) add_edge(s[top-1],s[top],dep[s[top]]-dep[s[top-1]]); if(t!=s[top]) add_edge(t,s[top],dep[s[top]]-dep[t]), s[top]=t; } s[++top]=x; } bool mark[n]; ll lmn[n],lmx[n],siz[n],sum[n]; ll pum,pmn,pmx; void dfs(int x) { lmn[x]=inf; lmx[x]=-inf; sum[x]=siz[x]=0; if(mark[x]) { lmx[x]=lmn[x]=0; siz[x]=1; } for(int i=head[x]; i; i=last[i]) { dfs(to[i]); pmn=min(pmn,lmn[x]+lmn[to[i]]+len[i]); pmx=max(pmx,lmx[x]+lmx[to[i]]+len[i]); pum+=sum[x]*siz[to[i]] +(siz[x]-mark[x])*sum[to[i]] +(siz[x]-mark[x])*len[i]*siz[to[i]]; lmn[x]=min(lmn[x],lmn[to[i]]+len[i]); lmx[x]=max(lmx[x],lmx[to[i]]+len[i]); sum[x]+=sum[to[i]]+siz[to[i]]*len[i]; siz[x]+=siz[to[i]]; } if(mark[x]) pum+=sum[x]; head[x]=0; mark[x]=0; } void print() { printf("asphaush tree: n"); static queue<int> q; q.push(1); while(!q.empty()) { int x=q.front(); q.pop(); for(int i=head[x]; i; i=last[i]) { printf("%d -> %d, length is %dn",x,to[i],len[i]); q.push(to[i]); } } } void solve() { //printf("nnew solving case: n"); scanf("%d",&k); for(int i=1; i<=k; ++i) { scanf("%d",&a[i]); mark[a[i]]=true; } sort(a+1,a+k+1,cmp); cnt=0; s[top=1]=1; for(int i=1; i<=k; ++i) ist(a[i]); for(; top>1; top--) add_edge(s[top-1],s[top],dep[s[top]]-dep[s[top-1]]); // print(); pum=0; pmn=inf; pmx=-inf; dfs(1); printf("%lld %lld %lldn",pum,pmn,pmx); } int main() { scanf("%d",&n); for(int x,y,i=n; --i; ) { scanf("%d%d",&x,&y); e[x].push_back(y); e[y].push_back(x); } pre(1,0); scanf("%d",&q); while(q--) solve(); return 0; } /* 10 2 1 3 2 4 1 5 2 6 4 7 5 8 6 9 7 10 9 5 2 5 4 2 10 4 2 5 2 2 6 1 2 6 1 */
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/605568.html