传送门：Takeout Delivering
标签：并查集
题目大意
给出一棵有n个点的树，编号分别为1,2,…,n，且这些点的权值为0~n-1的一个排列。现在对于k=0,1,…,n，你要找出找出一个连通子树，使得其中各点权值的mex值为k，且该连通子树在所有满足要求的连通子树中点数最多。
输入：第一行一个正整数n(1<=n<=1e6)，代表树的结点数。第二行n个非负整数，代表每个点的权值。接下来n-1行每行两个正整数，分别代表第i条边连接的两个点的编号。
输出：n+1个正整数，如果k=i时无解则输出0，否则输出所求连通子树的点数的最大值。
算法分析
- 首先我们要知道mex的含义，即一个集合中没出现过的最小非负正整数。现在要找一个点权mex值为k的连通子树，那就要保证权值为0~k-1的所有的点都出现在这棵树中，且权值为k的点绝对不能出现在这棵子树中。先考虑暴力的做法，我们要保证所得的子树包含的点最多，就只能在原树中断一条边。这一点很好证明，因为如果你断了两条边，就会将原树分成三个子树，已知其中一个0到k-1，一个子树包含k，那么剩下那个子树连接到哪就无关紧要，显然连接到所求的树中是最优解。
- 也就是说我们只要暴力枚举断哪条边再统计断开后的两个子树中包含的点权就能知道答案，但是这种做法肯定是会超时的。不过我们在写朴素做法的同时发现了一点，就是可以假设一个点为根节点，然后问题转化为求以各个点为根的子树所包含的点权区间与主树剩下部分点权的关系。既然mex值为k的子树中不能有权值为k的点，且点权取值范围为0~n-1，和k的范围一样，那我们完全可以反过来想，遍历到点权为x的点时就求k=x时的答案，这样只要跑一遍dfs就能解决问题了。
- 这样一来我们就知道了判断无解的条件，当点权为x的点所连接的子树中没有哪个是包含1到x-1中所有数的话，说明k=x时无解，反之答案就是那个子树的大小。所以我们先要预处理出以1为主树根节点时每个点为子树根节点时树的大小，这里记作sz[x]，则除去该子树后剩下的树大小为n-sz[x]。然后再利用树上启发式合并，就能在nlogn时间里跑遍每一个子树，然后再利用树状数组就能知道某子树中是否包含0到k-1中所有的数。用一个数组存下k=0,1,…,n-1时的答案，最后k=n时答案显然为n，直接输出即可。
代码实现
#include <iostream>
using namespace std;
#include <vector>
#define lowbit(x) (x)&(-x)
vector<int> g[1000010];
int n,son,mx,a[1000010],sz[1000010],wsn[1000010],cnt[1000010];
int LT[1000005];
int ans[1000010];
void update(int x,int d){x++;n++;while(x<=n){LT[x]+=d;x+=lowbit(x);}x--;n--;
}
int get(int l,int r){if(l>r)return 0;l++;r++;n++;int sum=0;l--;while(l){sum-=LT[l];l-=lowbit(l);}while(r){sum+=LT[r];r-=lowbit(r);}l--;r--;n--;return sum;
}
void dfs0(int x,int fa){sz[x]=1;for(auto &i:g[x])if(i!=fa){dfs0(i,x);if(sz[i]>sz[wsn[x]])wsn[x]=i;sz[x]+=sz[i];}
}
void cal(int x,int fa,int d){update(a[x],d);for(auto &i:g[x])if(i!=fa&&i!=son)cal(i,x,d);
}
void dfs1(int x,int fa,bool flag){for(auto &i:g[x])if(i!=fa&&i!=wsn[x])dfs1(i,x,0);if(wsn[x]){dfs1(wsn[x],x,1);son=wsn[x];}cal(x,fa,1);if(get(0,a[fa]-1)==a[fa])ans[a[fa]]=max(ans[a[fa]],sz[x]);if(get(0,a[x]-1)==0)ans[a[x]]=max(ans[a[x]],n-sz[x]);if(!flag){son=0;cal(x,fa,-1);}
}
int main(){int i,x;ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin>>n;for(i=1;i<=n;i++)cin>>a[i];for(i=2;i<=n;i++){cin>>x;g[x].emplace_back(i);g[i].emplace_back(x);}a[1000001]=1000001;dfs0(1,0);dfs1(1,1000001,1);for(i=0;i<n;i++)cout<<ans[i]<<' ';cout<<n;return 0;
}
