lp4577 FJOI2018 领导集团问题

我们尝试类比序列上的情况来看这一题。

对于序列上的情况,我们维护一个集合 \(S\) ,其中 \(S_i\) 表示,长度为 \(i\) 的最长不下降子序列的最后一项的最小值。 那么,对于新的点,我们考虑两种情况:它能加长序列,那么就加长;否则,就尽可能地更新最小值。

对于树上的情况,我们首先尝试考虑一种 \(O(n^2logn)\) 的做法。我们对于每一个节点维护一个集合 \(S_i\), 其中 \(S_{i,j}\) 表示仅用到这个节点及其子树内的所有点,能够构造的大小为 \(j\) 的集合的最小项的最大值。

如果我们把所有子节点的 \(S\) 都已经整合在一起了,那么更新根节点是比较容易的:类比于序列即可。 问题在于子节点要如何合并。

仔细观察,发现,子节点的合并是一个类似于归并的操作。 这样我们就有了一个 \(O(n^2logn)\) 的「高」效做法。

怎么优化这个做法呢? 我们不妨考虑重链剖分启发式合并。这样就将复杂度优化到了 \(O(nlog^2n)\) ,足以通过此题。 具体来说,我们对于每个节点开一个map,然后暴力合并。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<map>
#include<set>
using namespace std;
const int N=200005;
struct ee{
	int v;
	int nxt;
}e[N];
int h[N],et=0;
inline void add(int U,int V){
	e[++et]=(ee){V,h[U]};
	h[U]=et;
}
int w[N],sz[N],sn[N],dep[N],fa[N];
int id[N];
multiset<int> lst[N];
int n;
inline void dfs0(int X){
	sn[X]=0,sz[X]=1;
	for(int i=h[X];i;i=e[i].nxt){
		dfs0(e[i].v);
		sz[X]+=sz[e[i].v];
		if(sz[sn[X]]<sz[e[i].v]){
			sn[X]=e[i].v;
		}
	}
}
inline void dfs1(int X){
	if(sn[X]){
		dfs1(sn[X]);
		id[X]=id[sn[X]];
	}
	for(int i=h[X];i;i=e[i].nxt){
		if(e[i].v==sn[X]){
			continue;
		}
		dfs1(e[i].v);
		lst[id[X]].insert(lst[id[e[i].v]].begin(),lst[id[e[i].v]].end());
	}
	lst[id[X]].insert(w[X]);
	multiset<int>::iterator it=lst[id[X]].lower_bound(w[X]);
	if(it!=lst[id[X]].begin()){
		--it;lst[id[X]].erase(it);
	}
}
void init(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%d",&w[i]);
		id[i]=i;
	}
	int x;
	for(int i=2;i<=n;++i){
		scanf("%d",&x);
		fa[i]=x;add(x,i);
	}
	dfs0(1);
	dfs1(1);
	printf("%d\n",lst[id[1]].size());
}
int main(){
	init();
	return 0;
}

lp3313 SDOI2014 旅行

虽然这一题被划在主席树下面,但是一眼看过去这不就是树链剖分动态开点线段树的模板题么。
树链剖分后我们考虑对每一条链,建很多棵线段树,每棵线段树表示这条链上某种颜色的情况,然后大力合并。复杂度显然是对的。
关键是如何动态开点。本质上动态开点长得就和主席树差不多(这可能是为什么这题会被放在主席树下面),但是可能存在很多细节。
另:我的线段树区间查询写成依次单点查询,居然跑到了1.2s,让我一度以为是我常数问题…甚至差点卡进去了。精彩。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;

inline int rd(){
	char ch=getchar();int r=0;
	while(!isdigit(ch)){ch=getchar();}
	while(isdigit(ch)){r=r*10+ch-'0';ch=getchar();}
	return r;
}
const int N=100005;
inline int Max(int A,int B){
	return A>B?A:B;
}
inline void Swap(int &A,int &B){
	A^=B^=A^=B;
}
struct ee{
	int v;
	int nxt;
}e[N<<1];
int h[N],et=0;
inline void Eadd(int U,int V){
	e[++et]=(ee){V,h[U]};
	h[U]=et;
}
inline void add(int U,int V){
	Eadd(U,V);Eadd(V,U);
}
int n,m;
int val[N],clr[N],dep[N],sz[N],sn[N],fa[N],dfn[N],cnt=0,tp[N];
inline void dfs0(int X){
	dep[X]=dep[fa[X]]+1;sz[X]=1;sn[X]=0;
	for(int i=h[X];i;i=e[i].nxt){
		if(e[i].v==fa[X]){continue;}
		fa[e[i].v]=X;
		dfs0(e[i].v);
		if(sz[e[i].v]>sz[sn[X]]){
			sn[X]=e[i].v;
		}
		sz[X]+=sz[e[i].v];
	}
}
inline void dfs1(int X){
	dfn[X]=++cnt;
	if(sn[X]){tp[sn[X]]=tp[X];dfs1(sn[X]);}
	for(int i=h[X];i;i=e[i].nxt){
		if(e[i].v==sn[X]||e[i].v==fa[X]){continue;}
		tp[e[i].v]=e[i].v;dfs1(e[i].v);
	}
}
#define MID ((L+R)>>1)
struct Node{
	int l;int r;int sm;int mx;
}tr[4000005];
int rt[N];
int tcnt=0;
inline void chg(int &NW,int L,int R,int P,int V){
	if(!NW){NW=++tcnt;}
	if(L==R){tr[NW].sm=V,tr[NW].mx=V;return;}
	P<=MID?(chg(tr[NW].l,L,MID,P,V)):(chg(tr[NW].r,MID+1,R,P,V));
	tr[NW].sm=tr[tr[NW].l].sm+tr[tr[NW].r].sm;tr[NW].mx=Max(tr[tr[NW].l].mx,tr[tr[NW].r].mx);
}
inline int qryMx(int X,int A,int B,int L,int R){
	if(A>R||B<L||!X){return 0;}
	if(A<=L&&B>=R){return tr[X].mx;}//此处不应写成L==R 
	return Max((A<=MID?qryMx(tr[X].l,A,B,L,MID):0),(B>MID?qryMx(tr[X].r,A,B,MID+1,R):0));
}
inline int qrySm(int X,int A,int B,int L,int R){
	if(A>R||B<L||!X){return 0;}
	if(A<=L&&B>=R){return tr[X].sm;}
	return (A<=MID?qrySm(tr[X].l,A,B,L,MID):0)+(B>MID?qrySm(tr[X].r,A,B,MID+1,R):0);
}
inline void ADD(int X,int P,int V){
	chg(rt[X],1,n,P,V);
}
void init(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i){
		val[i]=rd(),clr[i]=rd();
	}
	int u,v;
	for(int i=1;i<n;++i){
		u=rd(),v=rd();
		add(u,v);
	}
	sz[0]=0;fa[1]=0;
	dfs0(1);
	tp[1]=1;
	dfs1(1);
	for(int i=1;i<=n;++i){
		ADD(clr[i],dfn[i],val[i]);
	}
	char ch[10];
	int x,y,c;
	for(int i=1;i<=m;++i){
		std::cin>>ch+1;
		switch(ch[2]){
			case 'C':{
				x=rd(),y=rd();
				ADD(clr[x],dfn[x],0);
				ADD(clr[x]=y,dfn[x],val[x]);
				break;
			}
			case 'W':{
				x=rd(),y=rd();
				ADD(clr[x],dfn[x],val[x]=y);
				break;
			}
			case 'S':{
				x=rd(),y=rd();
				int RT=0;c=clr[x];
				while(tp[x]!=tp[y]){
					if(dep[tp[x]]<dep[tp[y]]){Swap(x,y);}
					RT+=qrySm(rt[c],dfn[tp[x]],dfn[x],1,n);
					x=fa[tp[x]];
				}
				if(dep[x]<dep[y]){Swap(x,y);}
				RT+=qrySm(rt[c],dfn[y],dfn[x],1,n);
				printf("%d\n",RT);
				break;
			}
			case 'M':{
				x=rd(),y=rd();
				int RT=0;c=clr[x];
				while(tp[x]!=tp[y]){
					if(dep[tp[x]]<dep[tp[y]]){Swap(x,y);}
					RT=Max(RT,qryMx(rt[c],dfn[tp[x]],dfn[x],1,n));
					x=fa[tp[x]];
				}
				if(dep[x]<dep[y]){Swap(x,y);}
				RT=Max(RT,qryMx(rt[c],dfn[y],dfn[x],1,n));
				printf("%d\n",RT);
				break;
			}
		}
	}
}
int main(){
//	freopen("33132.in","r",stdin);
//	freopen("33132.ans","w",stdout);
	init();
	return 0;
}

lp2146 NOI2015 软件包管理器

简化题意:
存在一棵树,其上所有点的初始值为0。
存在两种操作,分别是,将一个点的所有父亲节点改为1,或者将一个点的所有儿子节点改为0。
要求维护这个修改,并能得知每一次修改的节点个数。
当然地,考虑到这棵树是静态的,我们可以预处理出每个点的子树大小和它到根的路径长度。
于是,问题就转化为:
把目标节点到根节点的所有点变成1,把目标节点的子树变成0,查询目标节点到根节点的1的数量,查询目标节点的子树的1的数量。
这个问题似乎有些困难。我们考虑它的弱化版,也就是只有目标节点到根节点的这样一种情况。
显然,只需要上一个树剖就可以解决问题。
那么加上子树修改呢?
我们意识到一个很有趣的事情,那就是,一棵子树中的点,在树剖后,仍然是DFS序序列上连续的一段。又,这一段的长度显然是子树大小,由此问题可解。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
#define Fv(i,X) for(int i=h[X];i;i=e[i].nxt) 

const int N=100005;
struct ee{
	int v;
	int nxt;
}e[N<<1];
int h[N],et=0;
int n,q;
inline void Eadd(int U,int V){
	e[++et]=(ee){V,h[U]};
	h[U]=et;
}
inline void add(int U,int V){
	Eadd(U,V);
	Eadd(V,U);
}
int sz[N],sn[N],dep[N],fa[N];
inline void dfs0(int X,int FA){
	sz[X]=1,sn[X]=0,dep[X]=dep[FA]+1,fa[X]=FA;
	Fv(i,X){
		if(e[i].v==FA){
			continue;
		}
		dfs0(e[i].v,X);
		sz[X]+=sz[e[i].v];
		if(sz[sn[X]]<sz[e[i].v]){
			sn[X]=e[i].v;
		}
	}
}
int dfn[N],cnt=0,tp[N]; 
inline void dfs1(int X,int FA,int TP){
	tp[X]=TP,dfn[X]=++cnt;
	if(sn[X]){
		dfs1(sn[X],X,TP);
	}
	Fv(i,X){
		if(e[i].v==FA||e[i].v==sn[X]){
			continue;
		}
		dfs1(e[i].v,X,e[i].v);
	}
}

#define MID ((L+R)>>1)
#define LS (X<<1)
#define RS (X<<1|1)
#define LEN (R-L+1)
int tr[N<<2],tg[N<<2];
inline void rnw(int X,int L,int R,int C){
	tr[X]=LEN*C,tg[X]=C+1;
}
inline void updt(int X,int L,int R){
	tr[X]=tr[LS]+tr[RS];
}
inline void pshd(int X,int L,int R){
	if(tg[X]){
		rnw(LS,L,MID,tg[X]-1),rnw(RS,MID+1,R,tg[X]-1);
		tg[X]=0;
	}
}
inline void chg(int X,int L,int R,int A,int B,int C){
	if(A<=L&&R<=B){
		rnw(X,L,R,C);
		return;
	}
	if(R<A||L>B){
		return;
	}
	pshd(X,L,R);
	chg(LS,L,MID,A,B,C),chg(RS,MID+1,R,A,B,C);
	updt(X,L,R);
}
inline int qry(int X,int L,int R,int A,int B){
	if(A<=L&&R<=B){
		return tr[X];
	}
	if(R<A||L>B){
		return 0;
	}
	pshd(X,L,R);
	return qry(LS,L,MID,A,B)+qry(RS,MID+1,R,A,B);
}

inline int dwqry(int X){
	return qry(1,1,n,dfn[X],dfn[X]+sz[X]-1);
}
inline void dwchg(int X){
	chg(1,1,n,dfn[X],dfn[X]+sz[X]-1,0);
}
inline int up(int X){
	int RT=0;
	while(X){
		RT-=qry(1,1,n,dfn[tp[X]],dfn[X]);
		RT+=dfn[X]-dfn[tp[X]]+1;
		chg(1,1,n,dfn[tp[X]],dfn[X],1);
		X=fa[tp[X]];
	}
	
	return RT;
}
void init(){
	scanf("%d",&n);
	int x;
	for(int i=1;i<n;++i){
		scanf("%d",&x);
		add(i+1,x+1);
	}
	dfs0(1,0);
	dfs1(1,0,1);
	scanf("%d",&q);
	char ch[10];
	for(int i=1;i<=q;++i){
		std::cin>>ch+1;
		scanf("%d",&x);
		++x;
		if(ch[1]=='i'){
			printf("%d\n",up(x));
		}else{
			printf("%d\n",dwqry(x));
			dwchg(x);
		}
	}
}
int main(){
	init();
	return 0;
}

lp2486 SDOI2011 染色

考虑这一题在链上的情况。
显然,可以建一棵线段树,修改是打标记下传,查询是左右相加特判左右相邻处颜色是否相同。
看起来在树上也可以这么做。但是仔细想想会发现不太对。
这是因为,根据树链剖分的原理,每两条剖开的链是独立查询的。
因此,在树上查询的时候,需要额外查询两个相接的链的接驳处的颜色是否相同。
这大概就做完了。

然后我们发现实时查询接驳处的颜色不仅很傻,而且容易错。
所以我们考虑开两个数组:lc和rc,储存一个区间内左端颜色和右端颜色。

另外就是链上接驳处的颜色问题。一种容易想到的方法是每一次记录它来的那个点,然后比较来的那个点和自身。
然而这么做同样是不仅傻而且容易错的。于是我们考虑另一种方法:每一次比较链顶和链顶的父亲这两个点,并将它的负贡献预先扣除。这样可以有效简化代码。

#include<iostream>
#include<cstdio>
#define Fv(i,X) for(int i=h[X];i;i=e[i].nxt)

inline void Swap(int &A,int &B){
    A^=B^=A^=B;
}
int n,m;
const int N=100005;
struct ee{
    int v;
    int nxt;
}e[N<<1];
int h[N],et=0;
inline void Eadd(int U,int V){
    e[++et]=(ee){V,h[U]};
    h[U]=et;
} 
inline void add(int U,int V){
    Eadd(U,V);
    Eadd(V,U);
}
int sn[N],sz[N],fa[N],dep[N];
inline void dfs0(int X,int FA){
    fa[X]=FA;sz[X]=1;dep[X]=dep[FA]+1;sn[X]=0;
    Fv(i,X){
        if(e[i].v==FA){
            continue;
        }
        dfs0(e[i].v,X);
        if(sz[e[i].v]>sz[sn[X]]){
            sn[X]=e[i].v;
        }
        sz[X]+=sz[e[i].v];
    }
}
int dfn[N],tp[N],cnt=0;
inline void dfs1(int X,int FA,int TP){
    dfn[X]=++cnt;tp[X]=TP;
    if(sn[X]){
        dfs1(sn[X],X,TP);
    }
    Fv(i,X){
        if(e[i].v==FA||e[i].v==sn[X]){
            continue;
        }
        dfs1(e[i].v,X,e[i].v);
    }
}
int clr[N];
#define MID ((L+R)>>1)
#define LS (X<<1)
#define RS (X<<1|1)
int tr[N<<2],tg[N<<2],val[N<<2],lc[N<<2],rc[N<<2];
inline void mdf(int X,int C){
    tr[X]=tg[X]=lc[X]=rc[X]=C;
    val[X]=1;
}
inline void pshd(int X,int L,int R){
	if(L==R){
		return;
	}
    if(tg[X]){
        mdf(LS,tg[X]),mdf(RS,tg[X]);
        tg[X]=0;
    }
}
inline int qryc(int X,int L,int R,int P){
    if(L==R){
        return tr[X];
    }
    pshd(X,L,R);
    return P<=MID?qryc(LS,L,MID,P):qryc(RS,MID+1,R,P);
}
inline void updt(int X,int L,int R){
    val[X]=(val[LS]+val[RS]-(rc[LS]==lc[RS]));
    lc[X]=lc[LS],rc[X]=rc[RS];
}
inline void chg(int X,int L,int R,int A,int B,int C){
    if(A<=L&&R<=B){
        mdf(X,C);
        return;
    }
    if(L>B||R<A){
        return;
    }
    pshd(X,L,R);
    chg(LS,L,MID,A,B,C);chg(RS,MID+1,R,A,B,C);
    updt(X,L,R);
}
inline int qryv(int X,int L,int R,int A,int B){
    if(A<=L&&R<=B){
        return val[X];
    }
    if(L>B||R<A){
        return 0;
    }
    pshd(X,L,R);
    return qryv(LS,L,MID,A,B)+qryv(RS,MID+1,R,A,B)-((A<=MID&&B>MID)?(rc[LS]==lc[RS]):0);
}
void init(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i){
        scanf("%d",&clr[i]);
    }
    int u,v;
    for(int i=1;i<n;++i){
        scanf("%d%d",&u,&v);
        add(u,v);
    }
    sz[0]=0,dep[0]=0;
    dfs0(1,0);
    dfs1(1,0,1);
    for(int i=1;i<=n;++i){
        chg(1,1,n,dfn[i],dfn[i],clr[i]);
    }
    char ch[4];
    int c,ans;
    for(int i=1;i<=m;++i){
        std::cin>>ch+1;
        switch(ch[1]){
            case 'Q':{
                scanf("%d%d",&u,&v);
                ans=0;
                while(tp[u]!=tp[v]){
                    if(dep[tp[u]]<dep[tp[v]]){
                        Swap(u,v);
                    }
                    ans+=qryv(1,1,n,dfn[tp[u]],dfn[u]);
                    ans-=(qryc(1,1,n,dfn[tp[u]])==qryc(1,1,n,dfn[fa[tp[u]]]));
                    u=fa[tp[u]];
                }
                if(dep[u]<dep[v]){
                    Swap(u,v);
                }
                ans+=qryv(1,1,n,dfn[v],dfn[u]);
                printf("%d\n",ans);
                break;
            }
            case 'C':{
                scanf("%d%d%d",&u,&v,&c);
                while(tp[u]!=tp[v]){
                    if(dep[tp[u]]<dep[tp[v]]){
                        Swap(u,v);
                    }
                    chg(1,1,n,dfn[tp[u]],dfn[u],c);
                    u=fa[tp[u]];
                }
                if(dep[u]<dep[v]){
                    Swap(u,v);
                }
                chg(1,1,n,dfn[v],dfn[u],c);
                break;
            }
        }
    }
}

int main(){
    init();
    return 0;
}

lp3676 小清新数据结构题

仔细考虑这道题,我们可以将问题转化为「修改」和「换根」两个操作。
对于修改操作,我们知道,每个点的权值对且仅对它到根节点上的这一条链上的每个点的答案产生贡献。
我们不妨令以1为根的情况下的每个点的修改前子树权值和为\(a_{i}\),修改对权值的改变为\(dlt\),那么可以计算得:
$$ans’=\sum(a_{i}+dlt)^2=\sum a_{i}^2+2dlt\times a_{i}+dlt^2\times len$$
故而,我们只需要用树链剖分套线段树维护树上区间平方和即可。

接下来我们考虑换根操作。
我们假设根从1换到了\(x\),那么子树权值大小会发生改变的仅有这条路径经过的点。我们不妨令换根后它们的子树权值和为\(b_{i}\),并有1~x为这条路径构成的序列,则我们发现答案会做出如下变动:
$$ans’=ans-\sum_{i=x}^1 a_{i}^2+\sum_{i=x}^1 b_{i}^2$$
我们发现,路径上的相邻点的子树的并集构成了整棵树。这也就意味着:
$$a_{i}+b_{i+1}=a_{0}=b_{x}$$
于是我们可以依此得到:
$$ans’=ans-\sum_{i=x}^1 a_{i}^2+b_x^2+\sum_{i=x-1}^1 (a_{0}-a_{i+1})^2$$
$$ans’=ans-\sum_{i=x}^2 a_{i}^2+(len-1)\times a_{0}^2-2a_{0}\times\sum_{i=x-1}^1 a_{i+1}+\sum_{i=x}^2a_{i}^2$$
$$ans’=(len-1)a_0^2-2a_{0}\sum_{i=x}^2a_{i}$$
同样也可以用树链剖分套线段树维护树上区间和与区间平方和。
注意:树剖不要写挂,下传给重儿子的链顶应该是本节点的链顶。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
#define Fv(i,X) for(int i=h[X];i;i=e[i].nxt)
typedef long long ll;

inline char rdc() {
 	static char buf[10000000], *p = buf, *end = buf;
	if (p == end) end = buf + fread(p = buf, sizeof(char), 10000000, stdin);
	return *(p++);
}

inline int rd(){
	int RT=0,c,f=1;
	while(!isdigit(c=rdc())){if(c=='-'){f=-1;}}
	do{RT=RT*10+c-'0';}while(isdigit(c=rdc()));
	return RT*f;
}

struct ee{
	int v;
	int nxt;
}e[400005];
int h[200005],et=0;
inline void Eadd(int U,int V){
	e[++et]=(ee){V,h[U]};
	h[U]=et;
}
inline void add(int U,int V){
	Eadd(U,V);
	Eadd(V,U);
}

int n,q;
ll val[200005],sm[200005];
int fa[200005],dep[200005],tp[200005],sn[200005],sz[200005];
int dfn[200005],loc[200005],cnt=0;

inline void dfs0(int X,int FA){
	dep[X]=dep[FA]+1;
	fa[X]=FA;
	sz[X]=1;
	sm[X]=val[X];
	Fv(i,X){
		if(e[i].v==FA){
			continue;
		}
		dfs0(e[i].v,X);
		sz[X]+=sz[e[i].v];
		if(sz[e[i].v]>sz[sn[X]]){
			sn[X]=e[i].v;
		}
		sm[X]+=sm[e[i].v];
	}
}

inline void dfs1(int X,int TP){
	loc[dfn[X]=++cnt]=X;
	tp[X]=TP;
	if(sn[X]){
		dfs1(sn[X],TP);
		//这里下传的应该是TP而非X...
		//树剖写挂了,我SB 
	}
	Fv(i,X){
		if(e[i].v==fa[X]||e[i].v==sn[X]){
			continue;
		}
		dfs1(e[i].v,e[i].v);
	}
}
#define MID ((L+R)>>1)
#define LS (X<<1)
#define RS (X<<1|1)
#define LEN (R-L+1)
#define LLEN (MID-L+1)
#define RLEN (R-MID)
struct data{
	ll sm;
	ll sm2;
	ll lzy;
}tr[2000005];

inline void rnw(int X,int Len,ll K){
	tr[X].sm2+=(K*K*Len+tr[X].sm*K*2);
	tr[X].sm+=(Len*K);
	tr[X].lzy+=K;
}
inline void pshd(int X,int L,int R){
	rnw(LS,LLEN,tr[X].lzy),rnw(RS,RLEN,tr[X].lzy);
	tr[X].lzy=0;
}
inline void updt(int X){
	tr[X].sm=tr[LS].sm+tr[RS].sm;
	tr[X].sm2=tr[LS].sm2+tr[RS].sm2;
}
inline void chg(int X,int L,int R,int A,int B,int V){
	if(L>=A&&R<=B){
		rnw(X,LEN,V);
		return;
	}
	pshd(X,L,R);
	if(A<=MID){
		chg(LS,L,MID,A,B,V);
	}
	if(B>MID){
		chg(RS,MID+1,R,A,B,V);
	}
	updt(X);
}
inline ll qrySm(int X,int L,int R,int A,int B){
	if(L>=A&&R<=B){
		return tr[X].sm;
	}
	if(L>B||R<A||B<A){
		return 0;
	}
	pshd(X,L,R);
	return qrySm(LS,L,MID,A,B)+qrySm(RS,MID+1,R,A,B);
}
inline ll qrySm2(int X,int L,int R,int A,int B){
	if(L>=A&&R<=B){
		return tr[X].sm2;
	}
	if(L>B||R<A||B<A){
		return 0;
	}
	pshd(X,L,R);
	return qrySm2(LS,L,MID,A,B)+qrySm2(RS,MID+1,R,A,B);
}
inline void build(int X,int L,int R){
	if(L==R){
		tr[X].sm=sm[loc[L]];
		tr[X].sm2=tr[X].sm*tr[X].sm;
		return;
	}
	build(LS,L,MID);build(RS,MID+1,R);
	updt(X);
}

void init(){
	n=rd(),q=rd();
	int u,v;
	for(int i=1;i<n;++i){
		u=rd(),v=rd();
		add(u,v);
	}
	for(int i=1;i<=n;++i){
		val[i]=rd();
	}
	dfs0(1,0);
	dfs1(1,1);
	build(1,1,n);
	int op,x,y;
	ll ans,a0=sm[1],sma,len;
	for(int i=1;i<=q;++i){
		op=rd();
		if(op==1){
			x=rd(),y=rd();
			y-=val[x];
			val[x]+=y;
			a0+=y;
			while(x){
				chg(1,1,n,dfn[tp[x]],dfn[x],y);
				x=fa[tp[x]];
			}
		}else{
			x=rd();
			len=sma=ans=0;
			ans=qrySm2(1,1,n,1,n);
			while(tp[x]!=tp[1]){
				len+=dfn[x]-dfn[tp[x]]+1;
				sma+=qrySm(1,1,n,dfn[tp[x]],dfn[x]);
				x=fa[tp[x]];
			}
			len+=dfn[x]-dfn[1];
			sma+=qrySm(1,1,n,dfn[1]+1,dfn[x]);
			printf("%lld\n",ans+a0*(len*a0-2*sma));
		}
	}
}
int main(){
	init();
	return 0;
}

CF487E Tourists

众所周知,圆方树是用来处理图上点双相关问题的。
同时,点双又是一个和简单路径密切相关的东西。故而这一题我们可以考虑用圆方树来处理。
我们发现,如果两点之间有多条简单路径,那么它们一定处于同一个点双中。所以,我们可以把原图转化为圆方树,这样就可以用树链剖分套线段树来求解询问了。
但是题目要求要修改点权,这要怎么办呢?

一个直观的想法是暴力修改每个点周围相邻的方点。然而事实上如果出现了个菊花套菊花套菊花图的话显然是会严重TLE的。
我们考虑一种动态维护一个方点的点值的算法。我们尝试对每个方点开一个mulitiset,每当修改一个点的点权的时候就把旧的点权删去然后插入新的点权,并更新方点点值。
然而,如果每个修改的圆点周围都有很多的方点的话,这种做法仍然有TLE的风险。我们考虑对于每个圆点,只更新它的父亲方点。
它对它的儿子方点的贡献,则在询问的时候统计。
这样复杂度就对了。
这就使用了圆方树上树链剖分套线段树解决了这道题。

注意:
树链剖分中更新最大孩子的部分,这里是son!不是sz!调了我一个晚上!

#pragma GCC optimize("Ofast")
#include<iostream>
#include<cstdio>
#include<algorithm> 
#include<set>
#define Fv(H,A,X) for(int A=H[X];A;A=e[A].nxt)

std::multiset<int> s[200005]; 

const int INF=2147483647;

inline int Max(int A,int B){
	return A>B?A:B;
}
inline int Min(int A,int B){
	return A<B?A:B;
}
inline void Swap(int &A,int &B){
	A^=B^=A^=B;
}

struct ee{
	int v;
	int nxt;
}e[2000005];
int h0[100005],h[200005],et=0;
inline void Eadd(int *H,int U,int V){
	e[++et]=(ee){V,H[U]};
	H[U]=et;
}
inline void add(int *H,int U,int V){
	Eadd(H,U,V);
	Eadd(H,V,U);
}


int dfn[200005],lw[100005];
//注意数组大小。 
int nm,cnt=0;
int st[100005],tp=0;
inline void dfs0(int X){
	dfn[X]=lw[X]=++cnt;
	st[++tp]=X;
	Fv(h0,i,X){
		if(!dfn[e[i].v]){
			dfs0(e[i].v);
			lw[X]=Min(lw[X],lw[e[i].v]);
			if(lw[e[i].v]==dfn[X]){
				++nm;
				for(int j=0;j!=e[i].v;--tp){
					j=st[tp];
					add(h,nm,j);
				}
				add(h,X,nm);
			}
		}else{
			lw[X]=Min(lw[X],dfn[e[i].v]);
		}
	}
}
int fa[200005],sz[200005],dep[200005],son[200005],top[200005],loc[200005];
inline void dfs1(int X,int FA){
	fa[X]=FA,dep[X]=dep[FA]+1,sz[X]=1;
	Fv(h,i,X){
		if(e[i].v!=FA){
			dfs1(e[i].v,X);
			sz[X]+=sz[e[i].v];
			if(sz[son[X]]<sz[e[i].v]){
				son[X]=e[i].v;
				//这里是son!不是sz!调了我一个晚上! 
			}
		}
	}
}
inline void dfs2(int X,int FA,int TP){
	dfn[X]=++cnt,loc[cnt]=X,top[X]=TP;
	if(son[X]){
		dfs2(son[X],X,TP);
	}
	Fv(h,i,X){
		if(e[i].v!=FA&&e[i].v!=son[X]){
			dfs2(e[i].v,X,e[i].v);
		}
	}
}

int n,m,q;
int a[200005];

#define MID (L+R>>1)
#define LS (X<<1)
#define RS (X<<1|1)

int tr[600005];
inline void bld(int X,int L,int R){
	if(L==R){
		tr[X]=a[loc[L]];
//		记得逆哈希 
		return;
	}
	bld(LS,L,MID);
	bld(RS,MID+1,R);
	tr[X]=Min(tr[LS],tr[RS]);
}

inline void chg(int X,int L,int R,int P,int V){
	if(L==R){
		tr[X]=V;
		return;
	}
	P<=MID?chg(LS,L,MID,P,V):chg(RS,MID+1,R,P,V);
	tr[X]=Min(tr[LS],tr[RS]);
}

inline int qry(int X,int L,int R,int A,int B){
	if(A>R||L>B){
		return INF;
	}
	if(A<=L&&R<=B){
		return tr[X];
	}
	return Min(qry(LS,L,MID,A,B),qry(RS,MID+1,R,A,B));
}

void init(){
	scanf("%d%d%d",&n,&m,&q);
	nm=n;
	for(int i=1;i<=n;++i){
		scanf("%d",&a[i]);
	}
	int u,v;
	for(int i=1;i<=m;++i){
		scanf("%d%d",&u,&v);
		add(h0,u,v);
	}
	dfs0(1);
	dfs1(1,0);
	cnt=0;
	dfs2(1,0,1);
	for(int i=1;i<=n;++i){
		if(fa[i]){
			s[fa[i]].insert(a[i]);
		}
	}
	for(int i=n+1;i<=nm;++i){
		a[i]=*s[i].begin();
	}
	
	bld(1,1,nm);
	char ch[3];
	int x,y;
	int ans;
	
	for(int i=1;i<=q;++i){
		scanf("%s%d%d",ch,&x,&y);
		if(ch[0]=='C'){
			chg(1,1,nm,dfn[x],y);
			if(fa[x]){
				u=fa[x];
				s[u].erase(s[u].lower_bound(a[x]));
				s[u].insert(y);
				if(a[u]!=*s[u].begin()){
					a[u]=*s[u].begin();
					chg(1,1,nm,dfn[u],a[u]);
				}
			}
			a[x]=y;
		}else{
			ans=INF;
			while(top[x]!=top[y]){
				if(dep[top[x]]<dep[top[y]]){
					Swap(x,y);
				}
				ans=Min(ans,qry(1,1,nm,dfn[top[x]],dfn[x]));
				x=fa[top[x]];
			}
			if(dfn[x]>dfn[y]){
				Swap(x,y);
			}
			ans=Min(ans,qry(1,1,nm,dfn[x],dfn[y]));
			if(x>n){
				ans=Min(ans,a[fa[x]]);
			}
			printf("%d\n",ans);
		}
	} 
}

int main(){
	init();
	return 0;
}

CF600E Lomsat gelral

一道树上启发式合并的例题。
首先考虑暴力的做法。统计每一个子节点的信息,然后传到父节点。
我们发现这样做的复杂度是\(O(n^2)\)的。显然,复杂度是错误的。
我们考虑修改统计子节点的顺序。
重链剖分有一个很有意义的性质:一个点通向根的路径上的轻边的数量最多不会超过\(log_n\)。这利用重链剖分的性质可以轻松用反证法证明。
那么,依据这个性质,我们可以统计轻边、上传重边。这也就意味着,对于每一次访问,如果它是一条轻边,那么就把它的信息统计完了清空;如果是一条重边,那么把它的信息上传。
例如,我们现在有一个节点\(X\),那么我们先计算它的所有轻节点,然后我们再计算它的重节点,最后将它除了重节点以外的地方都搜一遍,这样就获得了它的所有信息。
为什么这样做复杂度是对的呢?这就可以基于刚刚那个性质来证明了。具体地来说,一个节点会被清理信息,当且仅当它是一个节点下面的一个轻节点。也就是说,它被清空的次数就是它通向根的路径上轻边的数量。
由刚才那个性质可得,这个值是对数级的,所以复杂度是对的。
注意sm数组的tp的控制。

#include<iostream>
#include<cstdio>
struct ee{
	int v;
	int nxt;
}e[200005];
int h[100005],et=0;
inline void add(int U,int V){
	e[++et]=(ee){V,h[U]};
	h[U]=et;
}
int sn[100005],sz[100005],a[100005],cnt[100005];
bool kp[100005];
long long ans[100005];//ans表示每个节点的答案 
long long sm[100005];//sn表示出现次数为cnt次的颜色值的和 
int n;
inline void dfs1(int X,int FA){
	for(int i=h[X];i;i=e[i].nxt){
		if(e[i].v!=FA){
			dfs1(e[i].v,X);
		}
	}
	sz[X]=1;
	for(int i=h[X];i;i=e[i].nxt){
		if(e[i].v){
			sz[X]+=sz[e[i].v];
			if(sz[e[i].v]>sz[sn[X]]){
				sn[X]=e[i].v;
			}
		}
	}
}
int tp;
inline void rnw(int X,int FA,int V){
	sm[cnt[a[X]]]-=a[X];
	cnt[a[X]]+=V;
	sm[cnt[a[X]]]+=a[X];
	if(sm[tp+1]){
		++tp;
	}
	if(!sm[tp]){
		--tp;
	}
	for(int i=h[X];i;i=e[i].nxt){
		if(e[i].v!=FA&&!kp[e[i].v]){
			rnw(e[i].v,X,V);
		}
	}
}
inline void dfs2(int X,int FA,int isSn){
	for(int i=h[X];i;i=e[i].nxt){
		if(e[i].v!=FA&&e[i].v!=sn[X]){
			dfs2(e[i].v,X,0);
		}
	}
	if(sn[X]){
		dfs2(sn[X],X,1);
		kp[sn[X]]=1;
	}
	rnw(X,FA,1);
	kp[sn[X]]=0;
	ans[X]=sm[tp];
	if(!isSn){
		rnw(X,FA,-1);
	} 
}
void init(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%d",&a[i]);
	}
	int u,v;
	for(int i=1;i<n;++i){
		scanf("%d%d",&u,&v);
		add(u,v),add(v,u);
	}
	dfs1(1,0);
	dfs2(1,0,1);
	for(int i=1;i<=n;++i){
		printf("%lld ",ans[i]);
	}
}

int main(){
	init();
	return 0;
}