[SPOJ2666][ZJOI2007]捉迷藏Query on a tree IV(树链剖分)(论文做法)

题面

实际上,捉迷藏是Query on a tree IV的简化版。但区别只是捉迷藏的边权全部为1.这里把两个题合并起来写。

给定一棵包含 N 个结点的树，每个节点要么是黑色(亮灯)，要么是白色(不亮灯)。初始时每个节点都是白色。
要求模拟两种操作：
(1)改变某个结点的颜色。
(2)询问最远的两个白色结点之间的距离。

分析

做法来自2009年的国家集训队论文。捉迷藏的标准做法是利用括号序列的性质，但是括号序列是不能在有负边权的树上使用的。另外动态点分治似乎可做，不过论文中指出树链剖分实际上也是一种分治，只不过它的分治子树是一条重链，因此这两种做法本质是相同的

初始化

首先对树进行轻重链剖分。对于每个节点,记(d_1(x))和(d_2(x))分别表示该节点到子树中的白色节点的最长距离和次长距离,且两条路径仅在根节点处相交.如果不存在,则记为(- infin)

对于每条链上的节点,我们要维护以下三个变量:

(lmax): (x)所在重链的最浅节点到(x)子树中最远白点的距离
(rmax): (x)所重链的最深节点到(x)子树中最远白点的距离
(mlen):与(x)所在重链相交的,(x)子树中两个白点中间的路径的最长长度.

因为重链上节点的dfs序是连续的,那么重链对应一个区间([l,r]),记(id_{l})为dfs序为(l)的节点编号,最浅的节点为(id_l),最深的节点为(id_r)。因此我们可以对每条重链开一棵线段树来维护这几个变量。
记(dist(i,j))为(i,j)间距离,(p)为区间([l,r])对应的线段树节点,(lp,rp)为(p)的左右儿子。(mid=frac{l+r}{2}),那么有:

[lmax(p)=max(lmax(lp),dist(id_{mid+1},id_r)+lmax(rp)) ]

第二项就是把rp对应的一个前缀接到链([l,mid])上

[rmax(p)=max(rmax(rp),rmax(lp)+dist(id_{mid},id_r) ]

[mlen(p)=max(mlen(lp),mlen(rp),rmax(lp)+dist(id_{mid},id_{mid+1})+lmax(rp)) ]

由于是一条链,(dist)可以(O(1))算出。直接在线段树里 push_up即可.

void push_up(int x) {
		int l=tree[x].l,r=tree[x].r,mid=(l+r)>>1;
		tree[x].lmax=max(tree[lson(x)].lmax,dist[hash_dfn[mid+1]]-dist[hash_dfn[l]]+tree[rson(x)].lmax);//注意线段树是按dfs序存的
		tree[x].rmax=max(tree[rson(x)].rmax,dist[hash_dfn[r]]-dist[hash_dfn[mid]]+tree[lson(x)].rmax);
		tree[x].mlen=max(max(tree[lson(x)].mlen,tree[rson(x)].mlen),
		                 tree[lson(x)].rmax+dist[hash_dfn[mid+1]]-dist[hash_dfn[mid]]+tree[rson(x)].lmax);
	}

叶子节点的初始值可以这样设置
若(id_p)是黑点,有:
(lmax(p)=rmax(p)=d_1(id_p))
(mlen(p)=d_1(id_p)+d_2(id_p)) 因为(d_1,d_2)保证了交点只有一个,它们可以接起来

若(id_p)是白点,有
(lmax(p)=rmax(p)=max(d_1(id_p),0)) (把自己作为路径结尾,所以和0取max)
(mlen(p)=max(d_1(id_p)+d_2(id_p),d_1(id_p),0))
和 (可以把自己作为路径结尾,也可以两条路接在一起)

(d_1)和(d_2)可以用一个支持插入和删除任意元素的大根堆维护，可以用STL中的multiset实现.每个节点开一个这样的数据结构(h[x]),存储可能的路径长度。初始化的时候只需遍历(x)的轻儿子(y),用下面一层的重链更新上面的答案,插入(y)的(lmax+dist(x,y))即可。因此建树的时候一定要从深到浅建。

for(int i=head[x]; i; i=E[i].next) {
    int y=E[i].to;
    if(y!=fa[x]&&y!=son[x]){
        h[x].insert(tree[root[top[y]]].lmax+E[i].len);
        //累加下面一层重链的答案 
    }
}

处理查询

类似(d_1)和(d_2),我们维护一个全局的multisetans存储每条重链的答案(链顶lmax)。查询的时候输出最大值

处理修改

修改是最复杂的部分。我们沿着(x)往上跳,修改每一条重链。

(1)要删除当前重链对上方重链的影响,对于链顶节点父亲,我们在(h)中删去当前链顶的lmax+dist.

(2)修改线段树。如果是在被修改节点的重链上，就找到该节点,否则找到重链的最深节点。由于下面的重链已经修改完，我们可以用下面重链更新当前的答案。所以我们要在堆里插入新的(lmax+dist).然后求出新的(d_1,d_2)来更新(lmax,rmax,mlen).接着上推即可。

(3)在(ans)里删除旧的答案(链顶lmax),插入新的答案,

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<set>
#define maxn 100000
#define maxlogn 20
#define INF 0x3f3f3f3f
using namespace std;
int n,m;
struct my_heap { //支持删除任意元素的大根堆
	struct cmp {
		bool operator () (int p,int q) {
			return p>q;
		}
	};
	typedef multiset<int,cmp> hp;
	hp S;
	void insert(int v) {
		S.insert(v);
	}
	void del(int v) {
//		printf("delete %d
",v);
		hp::iterator it=S.lower_bound(v);
		if(it!=S.end()) S.erase(it);
	}
	int top() {
		if(S.empty()) return -INF;
		else return *S.begin();
	}
	int sec() { //
		int fir=top();
		if(fir!=-INF) {
			del(fir);
			int snd=top();
			insert(fir);
			return snd;
		} else return -INF;
	}
} h[maxn+5]/*每个节点到子树中的白点的距离*/,ans/*全局最大堆存储每条链的答案 */;

struct edge {
	int from;
	int to;
	int len;
	int next;
} E[maxn*2+5];
int head[maxn+5];
int esz;
void add_edge(int u,int v,int w) {
	esz++;
	E[esz].from=u;
	E[esz].to=v;
	E[esz].len=w;
	E[esz].next=head[u];
	head[u]=esz;
}

int light[maxn+5];//1为白点,2为黑点 
 
int tim;
int dist[maxn+5];
int sz[maxn+5],fa[maxn+5],son[maxn+5],top[maxn+5],dfn[maxn+5],hash_dfn[maxn+5],len[maxn+5]/*重链长度*/;
void dfs1(int x,int f) {
	sz[x]=1;
	fa[x]=f;
	for(int i=head[x]; i; i=E[i].next) {
		int y=E[i].to;
		if(y!=f) {
			dist[y]=dist[x]+E[i].len;
			dfs1(y,x);
			sz[x]+=sz[y];
			if(sz[y]>sz[son[x]]) son[x]=y;
		}
	}
}
void dfs2(int x,int t) {
	dfn[x]=++tim;
	hash_dfn[dfn[x]]=x;
	top[x]=t;
	len[t]++;
	if(son[x]) dfs2(son[x],t);
	for(int i=head[x]; i; i=E[i].next) {
		int y=E[i].to;
		if(y!=fa[x]&&y!=son[x]) dfs2(y,y);
	}
}
int root[maxn+5];
struct segment_tree {
#define lson(x) (tree[x].ls)
#define rson(x) (tree[x].rs)
	struct node { //由于对每个重链建一棵树,动态开点
		int l;
		int r;
		int ls;
		int rs;
		int lmax;//该节点所在重链的上端到子树中最远白点的距离
		int rmax;//该节点所在重链的下端到子树中最远白点的距离
		int mlen;//与该节点所在重链相交的,子树中两个白点中间的路径的最长长度.
	} tree[maxn*4+5];
	int ptr;
	void push_up(int x) {
		int l=tree[x].l,r=tree[x].r,mid=(l+r)>>1;
		tree[x].lmax=max(tree[lson(x)].lmax,dist[hash_dfn[mid+1]]-dist[hash_dfn[l]]+tree[rson(x)].lmax);//注意线段树是按dfs序存的
		tree[x].rmax=max(tree[rson(x)].rmax,dist[hash_dfn[r]]-dist[hash_dfn[mid]]+tree[lson(x)].rmax);
		tree[x].mlen=max(max(tree[lson(x)].mlen,tree[rson(x)].mlen),
		                 tree[lson(x)].rmax+dist[hash_dfn[mid+1]]-dist[hash_dfn[mid]]+tree[rson(x)].lmax);
	}
	void build(int &pos,int l,int r) {
		if(!pos) pos=++ptr;
		tree[pos].l=l;
		tree[pos].r=r;
		if(l==r) {
			int x=hash_dfn[l];
			for(int i=head[x]; i; i=E[i].next) {
				int y=E[i].to;
				if(y!=fa[x]&&y!=son[x]){
					h[x].insert(tree[root[top[y]]].lmax+E[i].len);
					//累加下面一层重链的答案 
				}
			}
			int d1=h[x].top();
			int d2=h[x].sec();
			//d1,d2为当前节点x到子树中白点的最大距离和次大距离,保证d1,d2只在x处相交 
			//初始时所有点都是白点,按白点的方法修改 
			tree[pos].lmax=tree[pos].rmax=max(d1,0);
			tree[pos].mlen=max(0,max(d1,d1+d2));
			return;
		}
		int mid=(l+r)>>1;
		build(lson(pos),l,mid);
		build(rson(pos),mid+1,r);
		push_up(pos);
	}
	void update(int pos,int x,int tp) {
		if(tree[pos].l==tree[pos].r) {
			if(x!=tp) h[x].insert(tree[root[tp]].lmax+dist[tp]-dist[x]));//插入新的答案 
			int d1=h[x].top();
			int d2=h[x].sec();
			if(light[x]) { //黑点 
				tree[pos].lmax=tree[pos].rmax=d1;
				tree[pos].mlen=d1+d2;
			} else { //白点 
				tree[pos].lmax=tree[pos].rmax=max(d1,0);//和自己凑成一对,所以和0取max
				tree[pos].mlen=max(0,max(d1,d1+d2));//可以和自己,也可以两条路接在一起
			}
			return;
		}
		int mid=(tree[pos].l+tree[pos].r)>>1;
		if(dfn[x]<=mid) update(lson(pos),x,tp);
		else update(rson(pos),x,tp);
		push_up(pos);
	}
}T;

void change(int x){
	int last=x; 
	while(x){//沿着重链往上跳 
		int tp=top[x];
		int p1=T.tree[root[tp]].mlen;
		if(fa[tp]){
			h[fa[tp]].del(T.tree[root[tp]].lmax+dist[tp]-dist[fa[tp]]);
			//删除当前点对上面重链答案的影响,等到跳到上面重链的时候再用线段树去更新 
		}
		T.update(root[tp],x,last);
		int p2=T.tree[root[tp]].mlen;
		if(p1!=p2){//答案发生改变 
			ans.del(p1);
			ans.insert(p2);
		}
		last=tp;
		x=fa[top[x]];
	}
}
int main() {
	int u,v,w; 
	int cnt=0;
	char op[maxn+5];
	scanf("%d",&n);
	cnt=n;
	for(int i=1;i<n;i++){
		scanf("%d %d %d",&u,&v,&w);
		add_edge(u,v,w);
		add_edge(v,u,w);
	}
	dfs1(1,0);
	dfs2(1,1);
	for(int i=n;i>=1;i--){//按照dfs序倒序,这样可以保证一条链是从下往上的 
		int x=hash_dfn[i];
		if(x==top[x]){
			T.build(root[x],dfn[x],dfn[x]+len[x]-1);
			ans.insert(T.tree[root[x]].mlen);
		}
	}
	scanf("%d",&m);
	for(int i=1;i<=m;i++){
		scanf("%s",op);
		if(op[0]=='C'){
			scanf("%d",&u);
			light[u]^=1;
			if(light[u]==0) cnt++;
			else cnt--;
			change(u); 
		}else{
			if(cnt==0) puts("They have disappeared.");
			else printf("%d
",ans.top());
		}
	}
}
/*
8
1 2 1
2 3 1
3 4 1
3 5 1
3 6 1
6 7 1
6 8 1
7
A
C 1
A
C 2
A
C 1
A
*/