当前位置: 代码迷 >> 综合 >> Educational Codeforces Round 47 (Rated for Div. 2)F详解
  详细解决方案

Educational Codeforces Round 47 (Rated for Div. 2)F详解

热度:83   发布时间:2023-10-21 06:16:18.0

题意:给出一棵树,对于结点x来说,dx,kdx,k表示与x的距离为k的它的孩子的个数,我们要找到dx,jdx,j,对于所有的k< j,dx,k<dx,jdx,k<dx,j,对于所有的k> j,dx,kdx,jdx,k≤dx,j,就是找到第一个最大的d。
做法也十分的暴力,我们在dfs的过程中,可以根据子节点碰到的每一层的节点个数来推出本层题目需要的d,但是如果节点很多的话,把子节点碰到的每一层的个数都赋值给父亲,会很浪费时间。所以我们可以运用树链剖分的一个思想,首先找到一个重儿子,将所有的轻儿子的内容都赋值给它,那么就相当于本层的d了。

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+5;
struct Edge
{int u,v;int nxt;Edge(int _u,int _v,int _nxt):u(_u),v(_v),nxt(_nxt){}Edge(){}
}edges[maxn*2];
int head[maxn],tot;
void addedge(int u,int v)
{edges[tot]=Edge(u,v,head[u]);head[u]=tot++;
}int dep[maxn];
int ans[maxn];
int mxson[maxn];
int cnt;
typedef pair<int,int>pii;
pii Ans[maxn];
map<int,int>Cut[maxn];
void Union(int T,int u)
{for(pii x:Cut[u]){Cut[T][x.first]+=x.second;if(Ans[T].first<Cut[T][x.first]){Ans[T]=make_pair(Cut[T][x.first],x.first);}else if(Ans[T].first==Cut[T][x.first]&&Ans[T].second>x.first){Ans[T]=make_pair(Cut[T][x.first],x.first);}}
}
int sz[maxn];
int rout[maxn];
void dfs(int u,int pre)
{dep[u]=dep[pre]+1;sz[u]=1;for(int i=head[u];~i;i=edges[i].nxt){int v=edges[i].v;if(v==pre)continue;dfs(v,u);sz[u]+=sz[v];if(sz[v]>sz[mxson[u]])mxson[u]=v;}rout[u]=rout[mxson[u]];if(!rout[u]){rout[u]=++cnt;Ans[cnt]=make_pair(1,dep[u]);}for(int i=head[u];~i;i=edges[i].nxt){int v=edges[i].v;if(v==pre||v==mxson[u])continue;Union(rout[u],rout[v]);}Cut[rout[u]][dep[u]]++;int T=rout[u];if(Ans[T].first<Cut[T][dep[u]]){Ans[T]=make_pair(Cut[T][dep[u]],dep[u]);}else if(Ans[T].first==Cut[T][dep[u]]&&Ans[T].second>dep[u]){Ans[T]=make_pair(Cut[T][dep[u]],dep[u]);}ans[u]=Ans[rout[u]].second;
}int main()
{memset(head,-1,sizeof(head));int n;scanf("%d",&n);int u,v;for(int i=1;i<n;i++){scanf("%d %d",&u,&v);addedge(u,v);addedge(v,u);}dfs(1,0);for(int i=1;i<=n;i++){printf("%d\n",ans[i]-dep[i]);}return 0;}
  相关解决方案