一个比较显然的做法:对每棵子树用线段树维护其中的深度,线段树合并即可。

  本来想用这个题学一下dsu on tree,结果还是弃疗了。

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
int read()
{
int x=,f=;char c=getchar();
while (c<''||c>'') {if (c=='-') f=-;c=getchar();}
while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();
return x*f;
}
#define N 1000010
int n,p[N],root[N],deep[N],ans[N],t=,cnt=;
struct data{int to,nxt;
}edge[N<<];
struct data2{int l,r,x,s;
}tree[N*];
void addedge(int x,int y){t++;edge[t].to=y,edge[t].nxt=p[x],p[x]=t;}
void up(int k)
{
if (tree[tree[k].l].s>=tree[tree[k].r].s)
tree[k].s=tree[tree[k].l].s,tree[k].x=tree[tree[k].l].x;
else tree[k].s=tree[tree[k].r].s,tree[k].x=tree[tree[k].r].x;
}
int merge(int x,int y,int l,int r)
{
if (!x||!y) return x|y;
if (l==r) tree[x].s+=tree[y].s;
else
{
int mid=l+r>>;
tree[x].l=merge(tree[x].l,tree[y].l,l,mid);
tree[x].r=merge(tree[x].r,tree[y].r,mid+,r);
up(x);
}
return x;
}
void ins(int &k,int x,int l,int r)
{
if (!k) k=++cnt;
if (l==r) {tree[k].s++,tree[k].x=x;return;}
int mid=l+r>>;
if (x<=mid) ins(tree[k].l,x,l,mid);
else ins(tree[k].r,x,mid+,r);
up(k);
}
void dfs(int k,int from)
{
for (int i=p[k];i;i=edge[i].nxt)
if (edge[i].to!=from)
{
deep[edge[i].to]=deep[k]+;
dfs(edge[i].to,k);
root[k]=merge(root[k],root[edge[i].to],,n);
}
ins(root[k],deep[k],,n);
ans[k]=tree[root[k]].x-deep[k];
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("dsu.in","r",stdin);
freopen("dsu.out","w",stdout);
const char LL[]="%I64d\n";
#else
const char LL[]="%lld\n";
#endif
n=read();
for (int i=;i<n;i++)
{
int x=read(),y=read();
addedge(x,y),addedge(y,x);
}
deep[]=;dfs(,);
for (int i=;i<=n;i++) printf("%d\n",ans[i]);
return ;
}

  

最新文章

  1. Questa Functional Verification-autocheck
  2. Code is not literature
  3. innodb 间隙锁
  4. PRINTDLG 结构体
  5. 关于64位Win7/Win 8 下怎么学习汇编语言
  6. 一年四个P(Project)
  7. Java的结构之美【1】——构造对象
  8. 【JBoss】Linux下JBoss服务器&quot;Too many open files&quot;的解决方法
  9. Problem H
  10. js 继承的简单易懂小例子
  11. ubuntu字符界面怎么设置中文显示和中文输入
  12. SSM-MyBatis-06:Mybatis中openSession到底做了什么
  13. SpringMvc通过@Value( ) 给静态变量注入值
  14. Django自定义分页
  15. 别再用&quot;while (!feof(file))&quot;来逐行读取txt文件了!
  16. 合肥学院第二届卓越IT-程序设计大赛E+J
  17. textarea的高度随内容变化而变化
  18. 【题解】Luogu SP1435 PT07X - Vertex Cover
  19. 在IIS中访问APS页面时提示:“最可能的原因使用的托管的处理程序,但是未安装或未完整安装asp.net“
  20. Nginx 随笔

热门文章

  1. Android学习之基础知识十一 —运用手机多媒体
  2. 学习CSS布局 - dispaly属性
  3. C. Report
  4. D. Imbalanced Array
  5. 在Linux下,如何分析一个程序达到性能瓶颈的原因
  6. wifidog源码分析 - 客户端检测线程
  7. 使用jdom进行xml解析,网络抓包
  8. C# 实现表单的自动化测试&lt;通过程序控制一个网页&gt;
  9. python3通过gevent.pool限制协程并发数量
  10. PowerBI开发 第十五篇:DAX 表达式(时间+过滤+关系)