树分治。对于一棵子树的根节点,至少有一条边与儿子相连的属于重边。对于一条轻边,它的贡献值是两端子树大小的乘积,所以,重边应该是贡献值最大的一边。

至于要求所有的点,进行深度优先搜索,因为移动一个点只会影响两个点的两个子树,这个可以维护。

在进行DP时,选择计算最大的重边的值,答案就是用所有的边贡献值减去树的重边值的和。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define LL long long
using namespace std; const int MAX=100010; int head[MAX],tol;
struct Edge{
int u,v,next;
}edge[MAX*2];
int n; void addedge(int u,int v){
edge[tol].u=u;
edge[tol].v=v;
edge[tol].next=head[u];
head[u]=tol++;
} int counts[MAX]; LL dp[MAX];
int weight1[MAX],weight2[MAX];
LL ans[MAX],tot[MAX],par[MAX]; void dfs(int u,int f){
counts[u]=1;
weight1[u]=weight2[u]=-1;
for(int e=head[u];e!=-1;e=edge[e].next){
int v=edge[e].v;
if(v!=f){
dfs(v,u);
counts[u]+=counts[v];
dp[u]+=dp[v];
if(weight1[u]==-1||(LL)(n-counts[v])*counts[v]>(LL)(n-counts[weight1[u]])*counts[weight1[u]]){
weight2[u]=weight1[u]; weight1[u]=v;
}
else if(weight2[u]==-1||(LL)(n-counts[v])*counts[v]>(LL)(n-counts[weight2[u]])*counts[weight2[u]]){
weight2[u]=v;
}
/// dp[u]+=(n-counts[v])*counts[v];
}
}
tot[u]=dp[u];
if(counts[u]>1){
dp[u]+=(LL)(n-counts[weight1[u]])*counts[weight1[u]];
}
} void dfs_ans(int u,int f){
for(int e=head[u];e!=-1;e=edge[e].next){
int v=edge[e].v;
if(v==f) continue;
if(v==weight1[u]){
LL num=max((LL)(n-counts[u])*counts[u],(LL)(n-counts[weight2[u]])*counts[weight2[u]]);
par[v]=tot[u]-dp[v]+par[u]+num;
}
else{
LL num=max((LL)(n-counts[u])*counts[u],(LL)(n-counts[weight1[u]])*counts[weight1[u]]);
par[v]=tot[u]-dp[v]+par[u]+num;
}
dfs_ans(v,u);
}
LL num=max((LL)(n-counts[weight1[u]])*counts[weight1[u]],(LL)(n-counts[u])*counts[u]);
ans[u]=par[u]+tot[u]+num;
} int main(){
while(scanf("%d",&n)!=EOF){
for(int i=1;i<=n;i++) head[i]=-1,counts[i]=0,dp[i]=0,par[i]=0;
tol=0;
int u,v;
for(int i=1;i<n;i++){
scanf("%d%d",&u,&v);
addedge(u,v);
addedge(v,u);
}
dfs(1,0);
dfs_ans(1,0);
LL ans_tot=0;
for(int i=1;i<=n;i++) ans_tot+=(LL)counts[i]*(n-counts[i]);
for(int i=1;i<=n;i++) cout<<ans_tot-ans[i]<<endl;
}
return 0;
}

  

最新文章

  1. Wpf之Xaml属性值和特性值(一)
  2. 纯灌水Linus主义
  3. 本地Git服务器的搭建及使用
  4. Spring概述
  5. (转)《深入理解java虚拟机》学习笔记2——Java内存溢出实例
  6. zoj 3460 Missile【经典建图&amp;&amp;二分】
  7. &lt;转载&gt;Wait and Waitpid
  8. 深入理解JVM(7)——线程安全和锁优化
  9. Python-读文件
  10. CCTV5 前端
  11. vue中复选框全选与反选
  12. UVALive - 7041 The Problem to Slow Down You (回文树)
  13. 【MySQL】锁——查看当前数据库锁请求的三种方法 20
  14. webpack介绍 安装 常用命令
  15. Java/JSP程序连接不上Mysql驱动问题解决方法
  16. ACM-ICPC 2017 Asia Urumqi:A. Coins(DP)
  17. 阿里云直播服务 sdk demo php
  18. MVC之CodeFirst
  19. Oracle rdbms Brush password
  20. python代码实现经典排序算法

热门文章

  1. Django day30 自定义配置settings文件,分页器,版本控制
  2. Netty(1) - 理解
  3. hadoop一主一从部署(1)
  4. matlab中增加Java VM 的堆空间(解决xml_io_tools出现的OutOfMemory问题)
  5. Jenkins-SVN + Maven + Docker
  6. AdminLTE介绍和zTree的简单使用
  7. Contact
  8. Linux(centOS7.2)+node+express初体验
  9. 如何让win32 c++窗口不出现在任务栏
  10. 【MySQL】RPM包安装