题目描述

假定我们有一棵有根树，其中每个点上有权。它被称为树堆当且仅当每个点的权值都大于等于它的所有孩子。

现在我们有一棵有根树，它的每个点上有权。我们可以不断对它进行如下的操作：选择一个非根结点vvv，删除vvv，然后将vvv的所有孩子连到vvv的父亲上。不断进行以上操作，此时可能一个子树会形成树堆。对树上的每个结点xxx，求出以xxx为根的子树以这种方式形成的树堆中(xxx不可删除)，结点最多的树堆的结点个数。

输入格式

第一行一个数nnn，表示树上的点数。

第二行nnn个数a0,a1,…,an−1a_0,a_1,\dots,a_{n-1}a0​,a1​,…,an−1​，aia_iai​表示iii的权值。

下面n−1n-1n−1行，每行两个数x,yx,yx,y，表示x,yx,yx,y之间有一条边。

树的根为000。保证输入形成一棵树。

输出格式

一行nnn个数，第iii个数表示以题目描述的方式生成的以i−1i-1i−1为根的数堆中，结点最多的树堆中的结点的个数。

样例输入

14
5 4 3 6 2 3 4 0 1 7 9 8 6 2
0 1
0 2
0 3
1 4
3 5
3 6
3 7
4 8
4 9
4 10
6 11
6 12
11 13

样例输出

9 3 1 5 2 1 2 1 1 1 1 2 1 1

数据范围

对于20%20\%20%的数据，1≤n≤201\leq n\leq 201≤n≤20
对于40%40\%40%的数据，1≤n≤50001\leq n\leq 50001≤n≤5000
对于60%60\%60%的数据，1≤n≤50001\leq n\leq 50001≤n≤5000
对于100%100\%100%的数据，1≤n≤1000001\leq n\leq 1000001≤n≤100000，0≤ai≤10000000000\leq a_i\leq 10000000000≤ai​≤1000000000

题解

前置知识：线段树合并

这道题其实就是让我们求树上的最长上升子序列。

首先，我们先考虑一个序列的最长上升子序列。假设已经求出了前iii个数的最长上升子序列，在加入第i+1i+1i+1个数时，在当前数列中找到第一个大于等于它的数。如果有，则用新加入的数替换；否则将新加入的数放在队尾。

树上呢？也一样。用权值线段树维护每一个点，线段树的sizsizsiz值就是该点所在子树中能选的最多的点的数量。

对于每个结点，先遍历其子树，然后将该结点的儿子结点的线段树合并到自己的线段树上。最后，在自己的线段树上找到第一个大于等于该结点的权值的位置。如果有，在权值线段树上这个位置减一，在该结点的权值所在位置加一；否则直接在该结点权值所在的位置加一。

最后，每个结点的答案即为该结点的权值线段树中小于等于该结点的权值的点的数量。时间复杂度为O(nlog⁡n)O(n\log n)O(nlogn)。

code

#include
using namespace std;
const int N=100000;
int n,x,y,tot=0,fl,a[100005],num[100005],d[200005],l[200005],r[200005],rt[100005],ans[100005];
struct node{int lc,rc,s;
}tr[10000005];
void add(int xx,int yy){l[++tot]=r[xx];d[tot]=yy;r[xx]=tot;
}
void merge(int &r1,int r2,int l,int r){if(!r1||!r2){r1=r1+r2;return;}if(l==r){tr[r1].s+=tr[r2].s;return;}int mid=(l+r)/2;merge(tr[r1].lc,tr[r2].lc,l,mid);merge(tr[r1].rc,tr[r2].rc,mid+1,r);tr[r1].s=tr[tr[r1].lc].s+tr[tr[r1].rc].s;
}
void pt(int &k,int l,int r,int z){if(!k) k=++tot;if(l==r){++tr[k].s;return;}int mid=l+r>>1;if(z<=mid) pt(tr[k].lc,l,mid,z);else pt(tr[k].rc,mid+1,r,z);tr[k].s=tr[tr[k].lc].s+tr[tr[k].rc].s;
}
void dele(int k,int l,int r,int z){if(!k) return;if(l==r){if(tr[k].s>0){--tr[k].s;fl=1;}return;}int mid=l+r>>1;if(z<=mid){dele(tr[k].lc,l,mid,z);if(!fl) dele(tr[k].rc,mid+1,r,z);}else dele(tr[k].rc,mid+1,r,z);tr[k].s=tr[tr[k].lc].s+tr[tr[k].rc].s;
}
int find(int k,int l,int r,int x,int y){if(!k) return 0;if(l>=x&&r<=y) return tr[k].s;if(l>y||r>1,re=0;if(x<=mid) re+=find(tr[k].lc,l,mid,x,y);if(y>mid) re+=find(tr[k].rc,mid+1,r,x,y);return re;
}
void dfs(int u,int fa){for(int i=r[u];i;i=l[i]){if(d[i]==fa) continue;dfs(d[i],u);merge(rt[u],rt[d[i]],1,N);}fl=0;dele(rt[u],1,N,a[u]+1);pt(rt[u],1,N,a[u]);ans[u]=find(rt[u],1,N,1,a[u]);
}
int main()
{scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&a[i]);num[i]=a[i];}sort(num+1,num+n+1);int gs=unique(num+1,num+n+1)-num-1;for(int i=1;i<=n;i++){a[i]=lower_bound(num+1,num+gs+1,a[i])-num;}for(int i=1;iscanf("%d%d",&x,&y);++x;++y;add(x,y);add(y,x);}tot=0;dfs(1,0);for(int i=1;i<=n;i++){printf("%d ",ans[i]);}return 0;
}