阔力梯的树(树上启发式合并+set)

传送门

人都傻了

d s u dsu dsu倒是模板,被 s e t set set的操作搞晕了…

s . l o w e r _ b o u n d ( i n t ) s.lower\_bound(int) s.lower_bound(int)返回一个大于等于查找元素的指针

s . e n d ( ) s.end() s.end() s e t set set的末尾位置,但是最后一个元素在末尾位置的前面 ! ! ! !!! !!!

l o w e r _ b o u n d lower\_bound lower_bound返回 s . e n d ( ) s.end() s.end()说明没找到这个元素

至于这里用 s e t set set也是有原因的,因为编号不重复,否则需要使用 m u l t i s e t multiset multiset


回到这道题,维护每个点的结实度

显然想知道一个点的结实度必须要把所有子节点的编号排成一个序列计算

但是直接计算是 O ( n 2 ) O(n^2) O(n2)

考虑到这个序列是可以合并的,答案也是小幅度修改,可以使用 d s u dsu dsu

使用 s e t set set来储存当前子树内的编号序列

加入一个编号时,直接 l o w e r _ b o u n d lower\_bound lower_bound找到插入的前驱后继,累加权值

删除时同理

这样就变成模板了

插入时分四种情况来写

s e t set set内元素个数只有 1 1 1

无前驱

无后继

有前驱和后继

删除同理

然后就直接套用 d s u _ o n _ t r e e dsu\_on\_tree dsu_on_tree的模板

#include bits/stdc++.h
using namespace std;
#define int long long
const int maxn = 2e5+10;
struct edge{
	int to,nxt;
}d[maxn]; int head[maxn],cnt=1;
void add(int u,int v){ d[++cnt] = (edge){v,head[u]},head[u] = cnt; }
int n,m,son[maxn],siz[maxn],sum,SON,ans[maxn];
void dfs(int u)
{
	siz[u] = 1;
	for(int i=head[u];i;i=d[i].nxt )
	{
		int v = d[i].to;
		dfs(v);
		siz[u] += siz[v];
		if( siz[v]siz[son[u]] )	son[u] = v;
	}
}
setints;
setint::iterator it;
int pre(setint::iterator it)	{ return *(--it); }
int nxt(setint::iterator it)	{ return *(++it); }
void ADD(int u)
{
	if( !s.size() )	{ s.insert(u); return; }
	it = s.lower_bound(u);//找到第一个大于等于的
	int pr = pre(it), nx = *it;
	if( it==s.begin() )	sum += (nx-u)*(nx-u);
	else if( it==s.end() )	sum += (u-pr)*(u-pr);
	else
	{
		sum -= (nx-pr)*(nx-pr);
		sum += (nx-u)*(nx-u)+(u-pr)*(u-pr);
	}
	s.insert(u);
}
void del(int u)
{
	if( s.size()==1 )	{ s.erase(u); return; }
	it = s.lower_bound(u);
	int pr = pre(it),nx = nxt(it);
	if( it==s.begin() )	sum -= (nx-*it)*(nx-*it);
	else if( *it==pre(s.end()) )	sum -= (pr-*it)*(pr-*it);
	else
	{
		sum += (nx-pr)*(nx-pr);
		sum -= (nx-u)*(nx-u)+(u-pr)*(u-pr);
	}
	s.erase(u);
}
void cal(int u,int type)
{
	( type?ADD(u):del(u) ); 
	for(int i=head[u];i;i=d[i].nxt )
	{
		int v = d[i].to;
		if( v!=SON )	cal( v,type );
	}
}
void dsu(int u,int type)
{
	for(int i=head[u];i;i=d[i].nxt )
	{
		int v = d[i].to;
		if( v!=son[u] )	dsu( v,0 );
	}
	if( son[u] )	dsu( son[u],1 ),SON = son[u];
	cal(u,1); ans[u] = sum; SON=0;
	if( !type )	cal(u,0);
}
signed main()
{
	cin  n;
	for(int i=2;i=n;i++)
	{
		int x; scanf("%lld",x);
		add(x,i);
	}
	dfs(1); dsu(1,1);
	for(int i=1;i=n;i++)	printf("%lld\n",ans[i] );
}
最新回复(0)
/jishuROsq4RVkoPvx5dHJqPDrQuqQNuhID8Gy3mBqCQ_3D_3D4834430
8 简首页