您的位置: 首页  >  IT文章  >  #点分树 or LCT#洛谷 4115 Qtree4 题目 分析（点分树） 代码 分析 代码

#点分树 or LCT#洛谷 4115 Qtree4 题目 分析（点分树） 代码 分析 代码

分类: IT文章 • 2022-06-08 21:07:16

两次LCT的Access操作就可以求LCA啦

给出一棵树，支持单点反色和查询全局最远白点

分析（点分树）

点分树的做法就是考虑点分树上的父亲把子树分成若干个部分，
那么所谓的白点直径可以把子树的最长链拼接起来
那么开三个可删堆，一个维护点分子树到父亲的距离，
一个维护父亲的答案，取第一个堆的最大值以保证其中每个值所属子树各不相同，
一个维护全局答案也就是直接用第二个堆的最大值和次大值合并起来，注意舍弃不必要的操作减小常数

代码

#include <cstdio>
#include <cctype>
#include <queue>
#include <algorithm>
#define rr register
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<23,stdin)),p1==p2?EOF:*p1++)
using namespace std;
const char S[22]={84,104,101,121,32,104,97,118,101,32,100,105,115,97,112,112,101,97,114,101,100,'.'};
const int N=100011; bool v[N]; struct node{int y,w,next;}e[N<<1];
int big[N],siz[N],SIZ,dfn[N],Siz[N],fat[N],root,as[N],tot;
char buf[1<<23],puf[1<<23],*p1,*p2; int nowp=-1;
int dep[N],et=1,two[18],lg[N<<1],f[N<<1][18],n,m,cnt,dis[N];
inline signed iut(){
	rr int ans=0,f=1; rr char c=getchar();
	while (!isdigit(c)) f=(c=='-')?-f:f,c=getchar();
	while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();
	return ans*f;
}
inline void Flush(){fwrite(puf,1,nowp+1,stdout),nowp=-1;}
inline void Putchar(char x){
	if (nowp==(1<<23)) Flush();
	puf[++nowp]=x;
}
inline void print(int ans){
	rr char dig[21]; rr int len=-1;
	do{
		dig[++len]=ans%10+48,ans/=10; 
	}while (ans);
	while (len>=0) Putchar(dig[len--]);
}
inline void Max(int &a,int b){a=a>b?a:b;}
inline void Min(int &a,int b){a=a<b?a:b;}
inline signed Get_Min(int x,int y){return dep[x]<dep[y]?x:y;}
inline signed lca(int x,int y){
	if (x>y) x^=y,y^=x,x^=y; rr int z=lg[y-x+1];
	return Get_Min(f[x][z],f[y-two[z]+1][z]);
}
inline signed Dis(int x,int y){
	rr int LCA=lca(dfn[x],dfn[y]);
	return dis[x]+dis[y]-2*dis[LCA];
}
inline void dfs(int x,int fa){
	siz[x]=1,big[x]=0;
	for (rr int i=as[x];i;i=e[i].next)
	if (e[i].y!=fa&&!v[e[i].y]){
		dfs(e[i].y,x);
		siz[x]+=siz[e[i].y];
		Max(big[x],siz[e[i].y]);
	}
	Max(big[x],SIZ-siz[x]);
	if (big[x]<=big[root]) root=x;
}
inline void dp(int x){
	v[x]=1,Siz[x]=big[0];
	for (rr int i=as[x];i;i=e[i].next)
	if (!v[e[i].y]){
		big[0]=SIZ=siz[e[i].y];
		dfs(e[i].y,root=0),
		fat[root]=x,dp(root);
	}
}
inline void Dfs(int x,int fa){
	f[dfn[x]=++tot][0]=x,dep[x]=dep[fa]+1;
	for (rr int i=as[x];i;i=e[i].next)
	if (e[i].y!=fa){
		dis[e[i].y]=dis[x]+e[i].w;
		Dfs(e[i].y,x),f[++tot][0]=x;
	}
}
struct Heap{
	priority_queue<int>q0,q1;
	inline signed Size(){return q0.size()-q1.size();}
	inline void Push(int x){q0.push(x);}
	inline void Pop(int x){q1.push(x);}
	inline signed Top(){
		while (!q1.empty()&&q0.top()==q1.top()) q0.pop(),q1.pop();
		return q0.top();
	}
	inline signed Pot(){
		rr int x=Top(); Pop(x);
		rr int ans=Top()+x;
		Push(x);
		return ans;
	}
}A[N],B[N],Ans;
inline void Ans_Pop(int x){if (A[x].Size()>1) Ans.Pop(A[x].Pot());}
inline void Ans_Push(int x){if (A[x].Size()>1) Ans.Push(A[x].Pot());}
inline void switch_off(int x){
	Ans_Pop(x),A[x].Push(0),Ans_Push(x);
	for (rr int X=x;fat[X];X=fat[X]){
		Ans_Pop(fat[X]);
		int DIS=Dis(fat[X],x);
		if (!B[X].Size())
			B[X].Push(DIS),A[fat[X]].Push(DIS);
		else{
			int now=B[X].Top(); B[X].Push(DIS);
			if (now<DIS)
			    A[fat[X]].Pop(now),A[fat[X]].Push(DIS);
		}
		Ans_Push(fat[X]);
	}
}
inline void switch_on(int x){
	Ans_Pop(x),A[x].Pop(0),Ans_Push(x);
	for (rr int X=x;fat[X];X=fat[X]){
		Ans_Pop(fat[X]);
		int now=B[X].Top(),DIS=Dis(fat[X],x);
		if (now>DIS) B[X].Pop(DIS);
		else {
			B[X].Pop(now);
		    if (!B[X].Size()) A[fat[X]].Pop(now);
		        else if (B[X].Top()<now)
				    A[fat[X]].Pop(now),A[fat[X]].Push(B[X].Top());
		}
		Ans_Push(fat[X]);
	}
}
signed main(){
	cnt=n=iut(),lg[0]=-1,two[0]=1,Ans.Push(0);
	for (rr int i=1;i<18;++i) two[i]=two[i-1]<<1;
	for (rr int i=1;i<n;++i){
		rr int x=iut(),y=iut(),w=iut();
		e[++et]=(node){y,w,as[x]},as[x]=et;
		e[++et]=(node){x,w,as[y]},as[y]=et;
	}
	for (rr int i=1;i<=et;++i) lg[i]=lg[i>>1]+1;
	big[0]=SIZ=n,Dfs(1,0);
	for (rr int j=1;j<=lg[tot];++j)
	for (rr int i=1;i+two[j]-1<=tot;++i)
	    f[i][j]=Get_Min(f[i][j-1],f[i+two[j-1]][j-1]);
	dfs(1,root=0),dfs(root,0),dp(root);
	for (rr int i=1;i<=n;++i) switch_off(i);
	for (rr int Q=iut();Q;--Q){
		rr char c=getchar();
		while (!isalpha(c)) c=getchar();
		if (c=='A'){
			if (!cnt) for (rr int o=0;o<22;++o) Putchar(S[o]);
			    else if (cnt==1) Putchar(48);
				    else print(Ans.Top());
			Putchar(10);
		}else{
			rr int x=iut(); v[x]^=1;
			if (!v[x]) --cnt,switch_on(x);
			    else ++cnt,switch_off(x);
		}
	}
	Flush();
	return 0;
}

分析

但是在 QTREE4 - Query on a tree IV 就一直TLE。

考虑LCT，维护深度最浅/最深的白点的最大距离，由于虚子树的答案也要维护所以用两个可删堆记录链和答案，然后一样拼接一下

但是SPOJ上只能用multiset过，我也不知道为什么

代码

#include <cstdio>
#include <cctype>
#include <queue>
using namespace std;
const int N=100011,inf=1e9;
struct node{int y,w,next;}e[N<<1];
int W[N],a[N],as[N],n,et=1,ans;
int iut(){
	int ans=0,f=1; char c=getchar();
	while (!isdigit(c)) f=(c=='-')?-f:f,c=getchar();
	while (isdigit(c)) ans=ans*10+c-48,c=getchar();
	return ans*f;
}
void print(int ans){
	if (ans>9) print(ans/10);
	putchar(ans%10+48);
}
struct Heap{
	priority_queue<int>q0,q1;
	int Size(){return q0.size()-q1.size();}
	void Push(int x){q0.push(x);}
	void Pop(int x){q1.push(x);}
	int Top(){
		while (!q1.empty()&&q0.top()==q1.top()) q0.pop(),q1.pop();
		return q0.top();
	}
	int Pot(){
		int x=Top(); Pop(x);
		int ans=Top()+x;
		Push(x);
		return ans;
	}
}A[N],B[N];
struct Splay{
	int lmx[N],rmx[N],mx[N],son[N][2],fat[N],w[N],rev[N],stac[N],TOP; 
	bool unroot(int x){return son[fat[x]][0]==x||son[fat[x]][1]==x;}
    bool Is_R(int x){return son[fat[x]][1]==x;}
	void pup(int x){
		w[x]=w[son[x][0]]+w[son[x][1]]+W[x];
		int xu=a[x],now=0;//与左子树相连实际是其祖先需要加上到父节点的边
		if (B[x].Size()) xu=max(xu,now=B[x].Top()),now=max(now,0);
		int L=max(xu,W[x]+rmx[son[x][0]]),R=max(xu,lmx[son[x][1]]);
		lmx[x]=max(lmx[son[x][0]],w[son[x][0]]+W[x]+R);
		rmx[x]=max(rmx[son[x][1]],w[son[x][1]]+L);
		mx[x]=max(L+lmx[son[x][1]],rmx[son[x][0]]+W[x]+R);
		mx[x]=max(mx[x],max(mx[son[x][0]],mx[son[x][1]]));
		if (A[x].Size()) mx[x]=max(mx[x],A[x].Top());
		if (B[x].Size()>1) mx[x]=max(mx[x],B[x].Pot());
		if (!a[x]) mx[x]=max(mx[x],now);
	}
	void Rev(int x){swap(son[x][0],son[x][1]),rev[x]^=1;}
	void pdown(int x){
		if (rev[x]){
			if (son[x][0]) Rev(son[x][0]);
			if (son[x][1]) Rev(son[x][1]);
			rev[x]=0;
		}
	}
	void rotate(int x){
		int Fa=fat[x],FFa=fat[Fa],wh=Is_R(x),t=son[x][wh^1];
		if (unroot(Fa)) son[FFa][Is_R(Fa)]=x;
		son[x][wh^1]=Fa,son[Fa][wh]=t;
		if (t) fat[t]=Fa; fat[Fa]=x,fat[x]=FFa;
		pup(Fa); 
	}
	void splay(int x){
		int y=x; stac[TOP=1]=y;
		while (unroot(y)) stac[++TOP]=y=fat[y];
		for (;TOP;--TOP) pdown(stac[TOP]);
		for (;unroot(x);rotate(x)){
			int Fa=fat[x];
			if (unroot(Fa)) rotate((Is_R(x)^Is_R(Fa))?x:Fa);
		}
		pup(x);
	}
	void Access(int x){
		for (int y=0;x;x=fat[y=x]){
			splay(x);
			if (son[x][1]) A[x].Push(mx[son[x][1]]),B[x].Push(lmx[son[x][1]]);
			if (y) A[x].Pop(mx[y]),B[x].Pop(lmx[y]);
			son[x][1]=y,pup(x);
		}
	}
	
}Tre;
void dfs(int x,int fa){
	for (int i=as[x];i;i=e[i].next)
	if (e[i].y!=fa){
		Tre.fat[e[i].y]=x,W[e[i].y]=e[i].w,dfs(e[i].y,x);
		A[x].Push(Tre.mx[e[i].y]),B[x].Push(Tre.lmx[e[i].y]);
	}
	Tre.pup(x); 
}
int main(){
	n=iut();
	for (int i=1;i<n;++i){
		int x=iut(),y=iut(),w=iut();
		e[++et]=(node){y,w,as[x]},as[x]=et;
		e[++et]=(node){x,w,as[y]},as[y]=et;
	}
	for (int i=0;i<=n;++i) Tre.lmx[i]=Tre.rmx[i]=Tre.mx[i]=-inf;
	dfs(1,0),ans=Tre.mx[1];
	for (int Q=iut();Q;--Q){
		char ch=getchar();
		while (!isalpha(ch)) ch=getchar();
		if (ch=='A'){
			if (ans<0) puts("They have disappeared.");
			    else print(ans),putchar(10);
		}else{
			int x=iut(); 
			Tre.Access(x),Tre.splay(x),
			a[x]=Tre.mx[0]-a[x],
			Tre.pup(x),ans=Tre.mx[x];
		}
	}
	return 0;
}

相关推荐