当前位置: 首页 > news >正文

记录这辈子见到的第一道从上到下的树上倍增

这道题先是浪费我半个下午做,做不出来有时好久看题解实现,气死我了。

题意。

给定一张 \(N\) 点的树,让我们考虑断掉每一条边,统计分裂出的两个子树的重心编号和之和。

要求 \(O(nlogn)\) 或更优的时间复杂度。

做法

这个咋做呢?我们可以在 OIwiki 中发现一些关于树的重心的神秘性质。

我这里粘贴 OIwiki 原文了。

  • 一棵有根树的重心一定在根结点所在的重链上。一棵树的重心一定是该树根结点重子结点对应子树的重心的祖先。

这就非常的贴心了。

我们发现我们很好判断了,若想知道一个点是不是重心,我们仅仅需要判断它的重儿子和除它子树以外的那一部分就行了。

既然判断非常简单了,我们就可以倍增来找了。

有多个怎么办?重心有多个的话两个必然是相邻的,再加一个判断就行了。

为了方便我们就从上往下倍增了,这样我们往重儿子走处理起来会很方便。

至于断边的影响,我们可以单独处理考上断边的倍增数组,把直接的下一个改成次重儿子不就行了。

这个样子就好做多了,我们在 dfs 的时候就可以把每一条边搞定。

代码如下↓

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MN=4e6+315;
int T, n, totsize;
struct Node{int nxt, to;
}node[MN];
int head[MN], tottt;
void insert(int u, int v){node[++tottt].to=v;node[tottt].nxt=head[u];head[u]=tottt; return;
}
int jump[MN][21], fa[MN];
int siz[MN], tmpsiz[MN];
int secw[MN], ans=0;
void init(){for(int i=1; i<=n; ++i){head[i]=secw[i]=siz[i]=tmpsiz[i]=fa[i]=0;for(int j=0; j<=20; ++j) jump[i][j]=0;	}
}
void Pre(){for(int j=1; j<=20; ++j){for(int i=1; i<=n; ++i){if(jump[i][j-1]) jump[i][j]=jump[jump[i][j-1]][j-1];}}
}
void update(int u){for(int j=1; j<=20; ++j){if(jump[u][j-1])jump[u][j]=jump[jump[u][j-1]][j-1];else jump[u][j]=0;}
}
int query(int u, int rt){for(int i=20; i>=0; --i){if(jump[u][i]&&siz[rt]-siz[jump[u][i]]<=siz[rt]/2){u=jump[u][i];}}return u;
}
bool check(int u, int tot){return max(siz[jump[u][0]],tot-siz[u])<=tot/2;
}
void dfs1(int u, int father){tmpsiz[u]=1; fa[u]=father;for(int i=head[u];i;i=node[i].nxt){int v=node[i].to;if(v==father) continue;dfs1(v,u); tmpsiz[u]+=tmpsiz[v];if(tmpsiz[v]>tmpsiz[jump[u][0]]){secw[u]=jump[u][0];jump[u][0]=v;}else if(tmpsiz[v]>tmpsiz[secw[u]]){secw[u]=v;}}siz[u]=tmpsiz[u];
}
void dfs2(int u, int father){int now, sav=jump[u][0];for(int i=head[u];i;i=node[i].nxt){int v=node[i].to;if(v==father) continue;if(v==sav) jump[u][0]=secw[u];else jump[u][0]=sav;if(siz[father]>siz[jump[u][0]]) jump[u][0]=father;update(u); now=u;siz[u]=totsize-tmpsiz[v];siz[v]=tmpsiz[v];fa[u]=fa[v]=0;now=query(u,u);ans+=check(now,siz[u])*now+check(fa[now],siz[u])*fa[now];now=v; now=query(v,v);ans+=check(now,siz[v])*now+check(fa[now],siz[v])*fa[now];fa[u]=v; dfs2(v,u);}jump[u][0]=sav; siz[u]=tmpsiz[u];fa[u]=father; update(u);
}
signed main(){ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);cin>>T; while(T--){init(); cin>>n;for(int i=1,u,v; i<n; ++i){cin>>u>>v; insert(u,v); insert(v,u);}ans=0; dfs1(1,0); Pre();totsize=siz[1]; dfs2(1,0);cout<<ans<<'\n';}return 0;
}
http://www.hskmm.com/?act=detail&tid=19207

相关文章:

  • 06.容器存储 - 教程
  • 1748:约瑟夫问题
  • Ansible + Docker 部署 Apache Nifi 1.28 单用户集群
  • 候机的队伍
  • Keil uVision5 设置 hex 输出路径,不放Objects目录下
  • 垃圾收集器G1ZGC详解
  • 2025海丰杯WP
  • 油猴脚本(tampermonkey)离线安装文件下载,带油猴(tampermonkey)插件清单
  • react useEffect Hook讲解
  • SentinelOne与MITRE ATTCK企业版2025评估的深度解析
  • 详细介绍:Docker的介绍
  • gen-ui-python
  • SPI和普通设计模式区别
  • 2025国内裱纸机厂家最新推荐排行榜:聚焦智能高速与全自动机型,权威精选综合实力 TOP3 厂家
  • 【题解】P13345 [EGOI 2025] IMO
  • 2025电线电缆厂家最新权威推荐榜:聚焦电线电缆实力企业,覆盖多场景需求助力精准选购
  • 9.27课后作业
  • 调度算法,上古三算法
  • 2025 年电脑租赁公司最新推荐排行榜:深度解析 TOP3 优质租电脑公司,助企业个人租赁电脑选择指南
  • 完整教程:✨WPF编程基础【1.2】:XAML中的属性
  • 学位论文中 公式的插入,格式调整、编号以及引用
  • 2025 北京羊蝎子餐厅推荐排行榜:TOP3最新必吃榜单,聚焦朝阳昌平东城等区域,揭秘北京羊蝎子餐厅必吃的门店!
  • 复刻江协激光触发器
  • Eurocrypt 2021 s Accepted Papers
  • Linux云服务器如何手动配置DNS?
  • Python 输入、输出的用法
  • 第一章——概论 - AlgosEng
  • 劝娃妈和娃不要学老人坐姿有感:老人无奈才坐成那样的。。AI协助分析很到位
  • 使用JOL查看对象布局
  • 集训队互测投题——封印