题目描述

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

现在我们有一棵有根树，它的每个点上有权。我们可以不断对它进行如下的操作：选择一个非根结点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

题解

线段树合并的做法在这篇博客。

不过下面这种方法不用线段树合并，只需要用vector来模拟multiset。

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

树上呢？也一样。对于每个节点，先遍历其子树，然后将该节点的儿子节点的最长上升子序列合并到自己的序列上。最后，在自己的序列上找到第一个大于该节点的权值的位置。如果有，将其在序列上删去，再把该节点的权值加在序列中；否则直接把该节点权值加在序列中。

这样做的话，每个节点都最多会花费O(n)O(n)O(n)的时间复杂度来合并，看起来是O(n2)O(n^2)O(n2)的，但是我们可以用一种特殊的方法来保证其时间复杂度为O(nlog⁡n)O(n\log n)O(nlogn)。

我们将每个点的各个儿子中子树的节点数量最多的儿子称为重儿子，重儿子连成的链称为重链。那么每次先遍历重儿子，再将当前节点的multiset序列和其重儿子的multiset序列互换。也就是说，重链上的点在重链中只会被放入序列一次。在这种情况下，我们考虑每个点被放入序列了多少次。每个点到根节点的路径上最多只会有log⁡n\log nlogn条重链，最多只会有log⁡n\log nlogn个祖先，所以只会被加log⁡n\log nlogn次，所有节点总共最多会被加入序列nlog⁡nn\log nnlogn次。

最后，每个结点的答案即为该结点的权值线段树中小于等于该结点的权值的点的数量。因为可能有权值相等的节点，所以要用multiset而不能用set。因为用了multiset，所以时间复杂度为O(nlog⁡2n)O(n\log^2 n)O(nlog2n)。

但这样会TLE。

code

#include
using namespace std;
int n,x,y,tot=0,a[100005],d[200005],l[200005],r[200005],siz[100005],son[100005],ans[100005];
multisets[100005];
void add(int xx,int yy){l[++tot]=r[xx];d[tot]=yy;r[xx]=tot;
}
void dfs1(int u,int fa){siz[u]=1;for(int i=r[u];i;i=l[i]){if(d[i]==fa) continue;dfs1(d[i],u);siz[u]+=siz[d[i]];if(siz[d[i]]>siz[son[u]]) son[u]=d[i];}
}
void dfs2(int u,int fa){multiset::iterator it;if(son[u]){dfs2(son[u],u);swap(s[u],s[son[u]]);}for(int i=r[u];i;i=l[i]){if(d[i]==fa||d[i]==son[u]) continue;dfs2(d[i],u);it=s[d[i]].begin();while(it!=s[d[i]].end()){s[u].insert(*it);++it;}s[d[i]].clear();}s[u].insert(a[u]);it=s[u].upper_bound(a[u]);if(it!=s[u].end()) s[u].erase(it);int c=0;for(it=s[u].begin();it!=s[u].end();++it){if(*it>a[u]) break;++c;	}//因为无法知道一个数在s[u]中是第几个，所以只能枚举ans[u]=c;
}
int main()
{scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&a[i]);}for(int i=1;iscanf("%d%d",&x,&y);++x;++y;add(x,y);add(y,x);}dfs1(1,0);dfs2(1,0);for(int i=1;i<=n;i++){printf("%d ",ans[i]);}return 0;
}

因为对于每个结点，都要查找在序列中小于等于这个结点的权值的点的个数。multiset不支持这种操作，但vector支持，所以我们可以用vector来模拟multiset，然后二分查找各个结点的答案即可。

插入一个结点的时间复杂度为O(log⁡n)O(\log n)O(logn)，查询的时间复杂度为O(log⁡n)O(\log n)O(logn)。所以时间复杂度为O(nlog⁡2n)O(n\log^2 n)O(nlog2n)。

下面就是AC代码。

code

#include
using namespace std;
int n,x,y,tot=0,a[100005],d[200005],l[200005],r[200005],siz[100005],son[100005],ans[100005];
vectors[100005];
void add(int xx,int yy){l[++tot]=r[xx];d[tot]=yy;r[xx]=tot;
}
void dfs1(int u,int fa){siz[u]=1;for(int i=r[u];i;i=l[i]){if(d[i]==fa) continue;dfs1(d[i],u);siz[u]+=siz[d[i]];if(siz[d[i]]>siz[son[u]]) son[u]=d[i];}
}
void dfs2(int u,int fa){vector::iterator it;int vt;if(son[u]){dfs2(son[u],u);swap(s[u],s[son[u]]);}for(int i=r[u];i;i=l[i]){if(d[i]==fa||d[i]==son[u]) continue;dfs2(d[i],u);for(it=s[d[i]].begin();it!=s[d[i]].end();++it){vt=(lower_bound(s[u].begin(),s[u].end(),*it)-s[u].begin());s[u].insert(s[u].begin()+vt,*it);}s[d[i]].clear();}if(!s[u].size()){s[u].push_back(a[u]);ans[u]=1;return;}if(*(s[u].end()-1)<=a[u]){s[u].push_back(a[u]);ans[u]=s[u].size();}else{vt=(upper_bound(s[u].begin(),s[u].end(),a[u])-s[u].begin());s[u].erase(s[u].begin()+vt);s[u].insert(s[u].begin()+vt,a[u]);ans[u]=vt+1;}
}
int main()
{scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&a[i]);}for(int i=1;iscanf("%d%d",&x,&y);++x;++y;add(x,y);add(y,x);}dfs1(1,0);dfs2(1,0);for(int i=1;i<=n;i++){printf("%d ",ans[i]);}return 0;
}