2021 CCPC 网络赛第二场 1011

题目

题意: 给定n个点的树，每个点具有各不相同的点权ai，我们是一只猴子，我们想要跳跃尽可能多的次数，跳跃的定义为:目的点v，起点u，v必须为u到v的最短路径上点权最大的点。求每个点分别作为起点时猴子跳跃的最大次数。 思路: 变成一只猴子(bushi)。任意发现，点权最大的点不能蹦到别的点，以其为起点最大次数为1.之后，我们可以删除该点及其相关的边，再在剩余连通块中找到点权最大的点，如法炮制。如果曾经与删除的连通块连通，加上相应的连通分量大小。 显然，删点删边的操作蒟蒻不会写。想到昨天robocom初赛最后一题，是离线+并查集，把删点的操作逆向转变成添点的操作，用并查集维护。 因此，我们可以按照点权从小到大依次添加点和相关的边。在添加边的过程中，点权大的点向点权小的点所在的连通块的father连边，重构一棵树。连边完成后，每个点的深度即为答案。 一个点跳跃到最大点权的位置后，就不能再跳了。我们以点权最大的点作为树根，每个点的最多跳跃次数即该点的深度。 时间复杂度: O(nlogn)

代码:

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define OldTomato ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
#define fir(i,a,b) for(int i=a;i