HIHO 16 C
2024-08-31 03:40:46
树分治。对于一棵子树的根节点,至少有一条边与儿子相连的属于重边。对于一条轻边,它的贡献值是两端子树大小的乘积,所以,重边应该是贡献值最大的一边。
至于要求所有的点,进行深度优先搜索,因为移动一个点只会影响两个点的两个子树,这个可以维护。
在进行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;
}
最新文章
- Wpf之Xaml属性值和特性值(一)
- 纯灌水Linus主义
- 本地Git服务器的搭建及使用
- Spring概述
- (转)《深入理解java虚拟机》学习笔记2——Java内存溢出实例
- zoj 3460 Missile【经典建图&;&;二分】
- <;转载>;Wait and Waitpid
- 深入理解JVM(7)——线程安全和锁优化
- Python-读文件
- CCTV5 前端
- vue中复选框全选与反选
- UVALive - 7041 The Problem to Slow Down You (回文树)
- 【MySQL】锁——查看当前数据库锁请求的三种方法 20
- webpack介绍 安装 常用命令
- Java/JSP程序连接不上Mysql驱动问题解决方法
- ACM-ICPC 2017 Asia Urumqi:A. Coins(DP)
- 阿里云直播服务 sdk demo php
- MVC之CodeFirst
- Oracle rdbms Brush password
- python代码实现经典排序算法
热门文章
- Django day30 自定义配置settings文件,分页器,版本控制
- Netty(1) - 理解
- hadoop一主一从部署(1)
- matlab中增加Java VM 的堆空间(解决xml_io_tools出现的OutOfMemory问题)
- Jenkins-SVN + Maven + Docker
- AdminLTE介绍和zTree的简单使用
- Contact
- Linux(centOS7.2)+node+express初体验
- 如何让win32 c++窗口不出现在任务栏
- 【MySQL】RPM包安装