Codeforces 600E. Lomsat gelral （线段树合并）

为什么线段树合并复杂度是O（nlogn）？因为每次merge都会删除一个节点，一开始节点是nlogn个，所以总复杂度就是O（nlogn）。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N=100005;
int a[N];

struct NODE
{
	int l,r,ls,rs,mx;
	ll cnt;
}tree[N*18];
int tot;
int root[N];
void init()
{
	tot=0;
}
int newnode(int l,int r)
{
	tot++;
	tree[tot]={l,r,0,0,0,0};
	return tot;
}
void up(int i)
{
	int ls=tree[i].ls,rs=tree[i].rs;
	tree[i].mx=max(tree[ls].mx,tree[rs].mx);
	tree[i].cnt=0;
	if (tree[ls].mx==tree[i].mx) tree[i].cnt+=tree[ls].cnt;
	if (tree[rs].mx==tree[i].mx) tree[i].cnt+=tree[rs].cnt;
}
int build(int l,int r,int x)
{
	int np=newnode(l,r);
	if (l==r)
	{
		tree[np].mx=1;
		tree[np].cnt=x;
		return np;
	}
	int mid=(l+r)/2;
	if (x<=mid) tree[np].ls=build(l,mid,x);
	else tree[np].rs=build(mid+1,r,x);
	up(np);
	return np;
}
int merge(int x,int y,int l,int r)
{
	if (x==0) return y;
	if (y==0) return x;
	if (l==r)
	{
		tree[x].mx+=tree[y].mx;
		return x;
	}
	int mid=(l+r)/2;
	tree[x].ls=merge(tree[x].ls,tree[y].ls,l,mid);
	tree[x].rs=merge(tree[x].rs,tree[y].rs,mid+1,r);
	up(x);
	return x;
}

vector<int>link[N];
ll f[N];
int n;
void dfs(int u,int fa)
{
	root[u]=build(1,n,a[u]);
	for (int i=0;i<link[u].size();i++)
	{
		int v=link[u][i];
		if (v==fa) continue;
		dfs(v,u);
		merge(root[u],root[v],1,n);
	}
	f[u]=tree[root[u]].cnt;
}
int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;i++) scanf("%d",&a[i]);
	for (int i=1;i<n;i++)
	{
		int x,y; scanf("%d%d",&x,&y);
		link[x].push_back(y);
		link[y].push_back(x);
	}
	init();
	dfs(1,1);
	for (int i=1;i<=n;i++) printf("%lld ",f[i]);
	for (int i=1;i<=n;i++) link[i].clear();

}
/*

http://codeforces.com/contest/600/problem/E

*/