CF1009F 题解

一、题目描述：

　　给定一棵以 1 为根，n 个节点的树。设 d(u,x) 为 u 的子树中到 u 距离为 x 的节点数。对于每个点，求一个最小的 k，使得 d(u,k) 最大。

 二、做题思路：

　　很明显是一个线段树合并的题，但是线段树里面放什么呢？设当前节点为 u，如果放的是距 u 距离为 x 的点的数量，那么在合并给父亲的时候就会出现 +1 的问题。但是如果存的是深度就没问题了，减去当前节点的深度即为答案。注意要动态开点，否则会炸空间。

三、完整代码：

 1 #include<iostream>
 2 #include<cstring>
 3 #define N 1000010
 4 #define ls(p) t[p].ls
 5 #define rs(p) t[p].rs
 6 using namespace std;
 7 int n,u1,v1,tot;
 8 int du[N],fa[N],ans[N],ro[N];
 9 struct Seg_tree{
10     int ls,rs;
11     int mx,sum;
12 }t[N*25];
13 struct EDGE{
14     int v,nxt;
15 }edge[N*2];
16 int head[N],cnt;
17 void add(int u,int v)
18 {
19     edge[++cnt].v=v;
20     edge[cnt].nxt=head[u];
21     head[u]=cnt;
22 }
23 void dfs1(int now,int d,int ff)
24 {
25     du[now]=d;fa[now]=ff;
26     for(int i=head[now];i!=-1;i=edge[i].nxt)
27         if(!du[edge[i].v])    dfs1(edge[i].v,d+1,now);
28 }
29 void push_up(int rt)
30 {
31     if(t[ls(rt)].sum>=t[rs(rt)].sum)
32         t[rt].sum=t[ls(rt)].sum,t[rt].mx=t[ls(rt)].mx;
33     if(t[ls(rt)].sum<t[rs(rt)].sum)
34         t[rt].sum=t[rs(rt)].sum,t[rt].mx=t[rs(rt)].mx;
35 }
36 void update(int &rt,int l,int r,int x)
37 {
38     if(!rt)    rt=++tot;
39     if(l==r)
40     {
41         t[rt].mx=l;
42         t[rt].sum++;
43         return ;
44     }
45     int mid=(l+r)>>1;
46     if(x<=mid)    update(ls(rt),l,mid,x);
47     if(x>mid)    update(rs(rt),mid+1,r,x);
48     push_up(rt);
49 }
50 int merge(int p,int q,int l,int r)
51 {
52     if(!q)    return p;
53     if(!p)    return q;
54     if(l==r)
55     {
56         t[p].sum+=t[q].sum;
57         return p;
58     }
59     int mid=(l+r)>>1;
60     ls(p)=merge(ls(p),ls(q),l,mid);
61     rs(p)=merge(rs(p),rs(q),mid+1,r);
62     push_up(p);
63     return p;
64 }
65 void dfs2(int now)
66 {
67     for(int i=head[now];i!=-1;i=edge[i].nxt)
68         if(edge[i].v!=fa[now])
69         {
70             dfs2(edge[i].v);
71             ro[now]=merge(ro[now],ro[edge[i].v],1,n);
72         }
73     ans[now]=t[ro[now]].mx-du[now];
74 }
75 int main()
76 {
77     ios::sync_with_stdio(false);
78     cin.tie(0);cout.tie(0);
79     cin>>n;
80     memset(head,-1,sizeof(head));
81     for(int i=1;i<n;i++)
82     {
83         cin>>u1>>v1;
84         add(u1,v1);
85         add(v1,u1);
86     }
87     dfs1(1,1,0);
88     for(int i=1;i<=n;i++)
89         update(ro[i],1,n,du[i]);
90     dfs2(1);
91     for(int i=1;i<=n;i++)
92         cout<<ans[i]<<'\n';
93     return 0;
94 }

四、写题心得：

　　拜托，这是紫题诶！！！真的很高兴的好吧！！！加油！