2019.01.08 codeforces 1009F. Dominant Indices(长链剖分)
2024-10-15 22:41:24
传送门
长链剖分模板题。
题意:给出一棵树,设fi,jf_{i,j}fi,j表示iii的子树中距离点iii距离为jjj的点的个数,现在对于每个点iii要求出使得fif_ifi取得最大值的那个jjj。
思路:有一个明显的状态转移式fi,j=∑v∈sonifv,j−1f_{i,j}=\sum_{v\in son_i}f_{v,j-1}fi,j=∑v∈sonifv,j−1,那么考虑对这棵树长链剖分,对于链上的信息用指针实现O(1)O(1)O(1)转移,而链与链之间的转移直接暴力转就行,因为总的链长是O(n)O(n)O(n)的因此这样做时间复杂度也为O(n)O(n)O(n)
代码:
#include<bits/stdc++.h>
#define ri register int
using namespace std;
inline int read(){
int ans=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return ans;
}
const int N=1e6+5;
int n,ftmp[N<<1],*f[N],*now=ftmp,hson[N],mdep[N],len[N],dep[N],fa[N],ans[N];
vector<int>e[N];
void dfs1(int p){
for(ri i=0,v;i<e[p].size();++i){
if((v=e[p][i])==fa[p])continue;
fa[v]=p,dep[v]=mdep[v]=dep[p]+1,dfs1(v),mdep[p]=max(mdep[p],mdep[v]);
if(mdep[v]>mdep[hson[p]])hson[p]=v;
}
len[p]=mdep[p]-dep[p]+1;
}
void dfs2(int p){
if(hson[p])f[hson[p]]=f[p]+1,dfs2(hson[p]),ans[p]=ans[hson[p]]+1;
f[p][0]=1;
for(ri i=0,v;i<e[p].size();++i){
if((v=e[p][i])==fa[p]||v==hson[p])continue;
f[v]=now,now+=len[v]+1,dfs2(v);
for(ri i=1;i<=len[v];++i){
f[p][i]+=f[v][i-1];
if((i<ans[p]&&f[p][i]>=f[p][ans[p]])||(i>ans[p]&&f[p][i]>f[p][ans[p]]))ans[p]=i;
}
}
if(f[p][ans[p]]==1)ans[p]=0;
}
int main(){
n=read();
for(ri i=1,u,v;i<n;++i)u=read(),v=read(),e[u].push_back(v),e[v].push_back(u);
dfs1(1),f[1]=now,now+=len[1],dfs2(1);
for(ri i=1;i<=n;++i)cout<<ans[i]<<'\n';
return 0;
}
最新文章
- bzoj 1858: [Scoi2010]序列操作
- String与Date、Timestamp互转
- bug汇总 (EF,Mvc,Wcf)
- IOS键盘弹出、隐藏
- SDUT 3258 Square Number 简单数学
- 我被eclipse的tomcat坑的经历
- 程序员取悦女朋友的正确姿势---Tips(iOS美容篇)
- scrollWidth,offsetWidth,clientWidth,width;scrollHeight,offsetHeight,clientHeight,height;offsetTop,scrollTop,top;offsetLeft,scrollLeft,left还有谁
- 用IDEA生成javadoc文档
- Struts源码之ValueStack
- Hive 口袋手册
- GSM:嗅探语音流量
- Ntrip协议简介(转)
- HTTP1.1协议-RFC2616-中文版课前资料收集
- C++中常用的std标准容器
- ubuntu12下subversion 1.6升级为1.8版本
- PHPNow升级PHP版本
- Python-css高级
- CodeForces - 1101D:GCD Counting (树分治)
- Material Design系列第四篇——Defining Shadows and Clipping Views
热门文章
- label标签的显示和隐式关联问题
- open suse linux 磁盘分区
- 5. Longest Palindromic Substring (DP)
- Codeforces Beta Round #31 (Div. 2, Codeforces format)
- Centos7安装Wkhtmltopdf -- nodejs将html转pdf
- ajax中的contendType和dataType知识点梳理
- echarts横向柱状图如果想打开网址
- To be a better me
- 如何将python中的List转化成dictionary
- sqlserver中对于特定数据字段定义特定的数据类型