bzoj 3611 [Heoi2014]大工程

bzoj 3611 [Heoi2014]大工程

​​ Description 国家有一个大工程，要给一个非常大的交通网络里建一些新的通道。 我们这个国家位置非常特殊，可以看成是一个单位边权的树，城市位于顶点上。 在 2 个国家 a,b 之间建一条新通道需要的代价为树上 a,b 的最短路径。 现在国家有很多个计划，每个计划都是这样，我们选中了 k 个点，然后在它们两两之间 新建 C(k,2)条 新通道。 现在对于每个计划，我们想知道： 1.这些新通道的代价和 2.这些新通道中代价最小的是多少 3.这些新通道中代价最大的是多少

Input

第一行 n 表示点数。 接下来 n-1 行，每行两个数 a,b 表示 a 和 b 之间有一条边。 点从 1 开始标号。 接下来一行 q 表示计划数。 对每个计划有 2 行，第一行 k 表示这个计划选中了几个点。 第二行用空格隔开的 k 个互不相同的数表示选了哪 k 个点。

Output

输出 q 行，每行三个数分别表示代价和，最小代价，最大代价。

Sample Input 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 Sample Output 3 3 3 6 6 6 1 1 1 2 2 2 2 2 2 HINT

n<=1000000 q<=50000并且保证所有k之和<=2*n Source

鸣谢佚名上传

建出虚树简单树形dp即可 蒟蒻我思想僵化 直接点分多个log

首先dp求最长最短链即可

然后求总长度 设dp[x]表示x节点的答案是多少于是有一个转移

dp[x]=∑y∈son[x]dp[y]+size[y]∗(m−size[y])∗(dis[y]−dis[x]) d p [ x ] = ∑ y ∈ s o n [ x ] d p [ y ] + s i z e [ y ] ∗ ( m − s i z e [ y ] ) ∗ ( d i s [ y ] − d i s [ x ] ) 直接求即可

#include#include#include#define ll long longusing namespace std;inline char gc(){ static char now[1<<16],*S,*T; if(T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;} return *S++;}inline int read(){ int x=0,f=1;char ch=gc(); while(!isdigit(ch)) {if (ch=='-') f=-1;ch=gc();} while(isdigit(ch)) x=x*10+ch-'0',ch=gc(); return x*f;}const int N=1e6+10;const int inf=0x3f3f3f3f;struct node{ int y,next;}data[N<<1],data1[N<<1];int h[N],dfn[N],cnt,dep[N],Log[N],fa[N][22],mn[N],mx[N],m,n,Q,ans1,ans2,a[N];bool mark[N];int size[N],h1[N];ll dp[N];int q[N],top,num;inline void dfs_init(int x){ dfn[x]=++cnt; for (int i=h1[x];i;i=data1[i].next){ int y=data1[i].y;if (y==fa[x][0]) continue; dep[y]=dep[x]+1;fa[y][0]=x; for (int j=1;j<=Log[dep[y]];++j) fa[y][j]=fa[fa[y][j-1]][j-1];dfs_init(y); }}inline int lca(int x,int y){ if (dep[x]=dep[q[top-1]]){ insert1(t,q[top]);--top; if (t!=q[top]) q[++top]=t;break; }insert1(q[top-1],q[top]);--top; }q[++top]=a[i]; }int x=q[1];for (int i=2;i<=top;++i) insert1(x,q[i]),x=q[i]; ans1=-inf;ans2=inf;dfs(q[1]); printf("%lld %d %d\n",dp[q[1]],ans2,ans1);}int main(){ freopen("bzoj3611.in","r",stdin); n=read();Log[0]=-1;for (int i=1;i<=n;++i) Log[i]=Log[i>>1]+1; for (int i=1;i

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。