自己怎么开网站,辽宁建设工程信息网查询截图,广东东莞划定多个高风险区,网站建设实习正题
题目链接:https://www.luogu.com.cn/problem/CF1009F 题目大意
以1为根的一棵树#xff0c;对于每个节点xxx求一个最小的kkk使得以xxx为根的子树中第kkk层的结点最多。 解题思路
我们先进行一次长链剖分#xff0c;对于一个长链我们可以发现如果每次往下做的话#…正题
题目链接:https://www.luogu.com.cn/problem/CF1009F 题目大意
以1为根的一棵树对于每个节点xxx求一个最小的kkk使得以xxx为根的子树中第kkk层的结点最多。 解题思路
我们先进行一次长链剖分对于一个长链我们可以发现如果每次往下做的话一个结点的的数组可以将下标都加一后丢到上一个结点做数组用指针可以O(1)O(1)O(1)直接实现这个过程。
然后再处理其他相连的链。这个和dusontreedus\ on\ treedus on tree的区别是这个暴力合并的时候只用枚举相连的长链上的点而不是子树所以时间复杂度是O(n)O(n)O(n) codecodecode
#includecstdio
#includecstring
#includealgorithm
using namespace std;
const int N1e610;
struct node{int to,next;
}a[N*2];
int n,tot,ls[N],len[N],ans[N];
int *f[N],*now,g[N],son[N];
void addl(int x,int y){a[tot].toy;a[tot].nextls[x];ls[x]tot;return;
}
void dfs1(int x,int fa){for(int ils[x];i;ia[i].next){int ya[i].to;if(yfa)continue;dfs1(y,x);if(len[y]len[son[x]])son[x]y;}len[x]len[son[x]]1;return;
}
void dfs2(int x,int fa){f[x][0]1;if(son[x]){f[son[x]]f[x]1;dfs2(son[x],x);ans[x]ans[son[x]]1;}for(int ils[x];i;ia[i].next){int ya[i].to;if(yfa||yson[x])continue;f[y]now;nowlen[y];dfs2(y,x);for(int j1;jlen[y];j){f[x][j]f[y][j-1];if(f[x][j]f[x][ans[x]]||f[x][ans[x]]f[x][j]jans[x])ans[x]j;}}if(f[x][ans[x]]1)ans[x]0;return;
}
int main()
{scanf(%d,n);for(int i1;in;i){int x,y;scanf(%d%d,x,y);addl(x,y);addl(y,x);}dfs1(1,0);nowf[1]g;nowlen[1];dfs2(1,0);for(int i1;in;i)printf(%d\n,ans[i]);
}
