Description

捉迷藏 Jiajia和Wind是一對恩愛的夫妻，并且他們有很多孩子。某天，Jiajia、Wind和孩子們決定在家裡玩

捉迷藏遊戲。他們的家很大且構造很奇特，由N個屋子和N-1條雙向走廊組成，這N-1條走廊的分布使得任意兩個屋

子都互相可達。遊戲是這樣進行的，孩子們負責躲藏，Jiajia負責找，而Wind負責操縱這N個屋子的燈。在起初的

時候，所有的燈都沒有被打開。每一次，孩子們隻會躲藏在沒有開燈的房間中，但是為了增加刺激性，孩子們會要

求打開某個房間的電燈或者關閉某個房間的電燈。為了評估某一次遊戲的複雜性，Jiajia希望知道可能的最遠的兩

個孩子的距離（即最遠的兩個關燈房間的距離）。我們将以如下形式定義每一種操作： C(hange) i 改變第i個房

間的照明狀态，若原來打開，則關閉；若原來關閉，則打開。 G(ame) 開始一次遊戲，查詢最遠的兩個關燈房間的

距離。

對于100%的資料， N ≤100000, M ≤500000。

Solution

蒟蒻的我并不會動态樹分治這種東西

發現我們實際上要求一棵虛樹的直徑。有一個結論是：兩棵樹通過加邊形成的新樹的直徑的兩個端點一定是原兩直徑四個端點中的兩個（繞，讨論一下共C(4,2)=6種情況

考慮用資瓷插入删除的splay維護這個東西。我們按dfs序為關鍵字，每次splay的時候向上合并倆兒子+自身共三棵樹的資訊。感覺這樣是沒有毛病的

然後我發現這道題好像并沒有-1的點。。

這份代碼交在洛谷上有70’，其中TLE的20‘可以通過rmq求lca搞定，剩下10’本寀基并不知道錯在了哪裡○|￣|_棄療

update

今天寫了30min的線段樹過了是什麼鬼Σ(っ °Д °;)っ

大體思路是一緻的，注意到我們并不需要對序列進行什麼奇妙的操作，是以一棵線段樹就可以解決問題了。

Code

線段樹

#include <stdio.h>
#include <string.h>
#include <algorithm>
#define rep(i,st,ed) for (int i=st;i<=ed;++i)

const int N=200005;

struct edge {int x,y,next;} e[N*2];
struct line {int x,y,len;} p[N<<2];

int pos[N],dfn[N],fa[N],size[N],bl[N],dep[N];
int ls[N],edCnt,tot;

bool v[N];

int read() {
	int x=0,v=1; char ch=getchar();
	for (;ch<'0'||ch>'9';v=(ch=='-')?(-1):(v),ch=getchar());
	for (;ch<='9'&&ch>='0';x=x*10+ch-'0',ch=getchar());
	return x*v;
}

void add_edge(int x,int y) {
	e[++edCnt]=(edge) {x,y,ls[x]}; ls[x]=edCnt;
	e[++edCnt]=(edge) {y,x,ls[y]}; ls[y]=edCnt;
}

void dfs1(int now) {
	size[now]=1;
	for (int i=ls[now];i;i=e[i].next) {
		if (e[i].y==fa[now]) continue;
		dep[e[i].y]=dep[now]+1; fa[e[i].y]=now;
		dfs1(e[i].y); size[now]+=size[e[i].y];
	}
}

void dfs2(int now,int up) {
	pos[now]=++pos[0]; dfn[pos[0]]=now;
	bl[now]=up; int mx=0;
	for (int i=ls[now];i;i=e[i].next) {
		if (e[i].y!=fa[now]&&size[e[i].y]>size[mx]) mx=e[i].y;
	}
	if (!mx) return ;
	dfs2(mx,up);
	for (int i=ls[now];i;i=e[i].next) {
		if (e[i].y!=fa[now]&&e[i].y!=mx) dfs2(e[i].y,e[i].y);
	}
}

int get_lca(int x,int y) {
	for (;bl[x]!=bl[y];) {
		if (dep[bl[x]]<dep[bl[y]]) std::swap(x,y);
		x=fa[bl[x]];
	}
	return (dep[x]<dep[y])?x:y;
}

int get_dis(int x,int y) {
	if (!x||!y) return 0;
	return dep[x]+dep[y]-2*dep[get_lca(x,y)];
}

line merge(line a,line b) {
	if (!a.x&&!a.y) return b;
	if (!b.x&&!b.y) return a;
	int x1=a.x,x2=b.x,y1=a.y,y2=b.y;
	line ret=(line) {x1,y1,a.len};
	if (get_dis(x1,x2)>ret.len) {
		ret.len=get_dis(x1,x2); ret.x=x1,ret.y=x2;
	}
	if (get_dis(x1,y2)>ret.len) {
		ret.len=get_dis(x1,y2); ret.x=x1,ret.y=y2;
	}
	if (get_dis(x2,y1)>ret.len) {
		ret.len=get_dis(x2,y1); ret.x=x2,ret.y=y1;
	}
	if (get_dis(x2,y2)>ret.len) {
		ret.len=get_dis(x2,y2); ret.x=x2,ret.y=y2;
	}
	if (get_dis(y1,y2)>ret.len) {
		ret.len=get_dis(y1,y2); ret.x=y1,ret.y=y2;
	}
	return ret;
}

void modify(int now,int tl,int tr,int x) {
	if (tl==tr) {
		if (v[x]) p[now]=(line) {0,0,0},tot--;
		v[x]^=1;
		if (v[x]) p[now]=(line) {dfn[x],dfn[x],0},tot++;
		return ;
	}
	int mid=(tl+tr)>>1;
	if (x<=mid) modify(now<<1,tl,mid,x);
	else modify(now<<1|1,mid+1,tr,x);
	p[now]=merge(p[now<<1],p[now<<1|1]);
}

int main(void) {
	freopen("data.in","r",stdin);
	freopen("myp.out","w",stdout);
	int n=read(); tot=0;
	rep(i,2,n) add_edge(read(),read());
	dfs1(dep[1]=1); dfs2(1,1);
	rep(i,1,n) modify(1,1,n,pos[i]);
	for (int T=read(),opt,x;T--;) {
		for (opt=getchar();opt!='G'&&opt!='C';opt=getchar()) ;
		if (opt=='G') {
			if (tot==1) puts("0");
			else if (tot==0) puts("-1");
			else printf("%d\n", p[1].len);
		} else {
			x=read();
			modify(1,1,n,pos[x]);
		}
	}
	return 0;
}

splay

#pragma GCC optimize(3)
#include <stdio.h>
#include <string.h>
#include <algorithm>
#define rep(i,st,ed) for (int i=st;i<=ed;++i)

const int N=200005;

struct edge {int y,next;} e[N*2];
struct line {int x,y,len;} ;
struct treeNode {int son[2],fa; line p;} t[N];

int dep[N],pos[N],bl[N],size[N],fa[N];
int ls[N],root,edCnt,n;

bool v[N];

int read() {
	int x=0,v=1; char ch=getchar();
	for (;ch<'0'||ch>'9';v=(ch=='-')?(-1):(v),ch=getchar());
	for (;ch<='9'&&ch>='0';x=x*10+ch-'0',ch=getchar());
	return x*v;
}

void add_edge(int x,int y) {
	e[++edCnt]=(edge) {y,ls[x]}; ls[x]=edCnt;
	e[++edCnt]=(edge) {x,ls[y]}; ls[y]=edCnt;
}

int get_lca(int x,int y) {
	for (;bl[x]!=bl[y];) {
		if (dep[bl[x]]<dep[bl[y]]) std:: swap(x,y);
		x=fa[bl[x]];
	}
	return (dep[x]<dep[y])?x:y;
}

int get_dis(int x,int y) {
	if (!(x*y)) return 0;
	int lca=get_lca(x,y);
	return dep[x]+dep[y]-dep[lca]*2;
}

line merge(line a,line b) {
	int x1=a.x,x2=b.x,y1=a.y,y2=b.y;
	line ret=(line) {x1,y1,a.len};
	if (get_dis(x1,x2)>ret.len) {
		ret.len=get_dis(x1,x2); ret.x=x1,ret.y=x2;
	}
	if (get_dis(x1,y2)>ret.len) {
		ret.len=get_dis(x1,y2); ret.x=x1,ret.y=y2;
	}
	if (get_dis(x2,y1)>ret.len) {
		ret.len=get_dis(x2,y1); ret.x=x2,ret.y=y1;
	}
	if (get_dis(x2,y2)>ret.len) {
		ret.len=get_dis(x2,y2); ret.x=x2,ret.y=y2;
	}
	if (get_dis(y1,y2)>ret.len) {
		ret.len=get_dis(y1,y2); ret.x=y1,ret.y=y2;
	}
	return ret;
}

void push_up(int x) {
	t[x].p=(line) {x,x,0};
	if (x>n) t[x].p=(line) {0,0,0};
	if (t[x].son[0]) t[x].p=merge(t[x].p,t[t[x].son[0]].p);
	if (t[x].son[1]) t[x].p=merge(t[x].p,t[t[x].son[1]].p);
}

void rotate(int x) {
	int y=t[x].fa; int z=t[y].fa;
	int k=t[y].son[1]==x;
	t[x].fa=z; t[z].son[t[z].son[1]==y]=x;
	t[y].son[k]=t[x].son[!k]; t[t[x].son[!k]].fa=y;
	t[y].fa=x; t[x].son[!k]=y;
	push_up(y); push_up(x);
}

void splay(int x,int goal=0) {
	for (;t[x].fa!=goal;) {
		int y=t[x].fa; int z=t[y].fa;
		if (z!=goal) {
			if ((t[z].son[1]==y)^(t[y].son[1]==x)) rotate(x);
			else rotate(y);
		}
		rotate(x);
	}
	if (!goal) root=x;
}

int get_pre(int x) {
	splay(x);
	int y=t[x].son[0];
	for (;t[y].son[1];) y=t[y].son[1];
	// splay(y);
	return y;
}

int get_nex(int x) {
	splay(x);
	int y=t[x].son[1];
	for (;t[y].son[0];) y=t[y].son[0];
	// splay(y);
	return y;
}

void del(int x) {
	int pre=get_pre(x);
	int nex=get_nex(x);
	splay(pre); splay(nex,pre);
	t[t[nex].son[0]].fa=0;
	t[t[nex].son[0]].p=(line) {t[nex].son[0],t[nex].son[0],0};
	t[nex].son[0]=0; push_up(nex);
	splay(nex);
}

void ins(int x) {
	int y=root,fa=0;
	for (;y;) fa=y,y=t[y].son[pos[x]>pos[y]];
	t[x].fa=fa; t[fa].son[pos[x]>pos[fa]]=x;
	t[x].p=(line) {x,x,0};
	splay(x);
}

void dfs1(int now) {
	size[now]=1;
	for (int i=ls[now];i;i=e[i].next) {
		if (e[i].y==fa[now]) continue;
		fa[e[i].y]=now; dep[e[i].y]=dep[now]+1;
		dfs1(e[i].y); size[now]+=size[e[i].y];
	}
}

void dfs2(int now,int up) {
	bl[now]=up; pos[now]=++pos[0];
	int mx=0;
	for (int i=ls[now];i;i=e[i].next) {
		if (e[i].y!=fa[now]&&size[e[i].y]>size[mx]) mx=e[i].y;
	}
	if (!mx) return ;
	dfs2(mx,up);
	for (int i=ls[now];i;i=e[i].next) {
		if (e[i].y!=fa[now]&&e[i].y!=mx) dfs2(e[i].y,e[i].y);
	}
}

int main(void) {
	freopen("data.in","r",stdin);
	freopen("myp.out","w",stdout);
	n=read(); int tot=n;
	rep(i,2,n) add_edge(read(),read());
	dfs1(dep[1]=1); dfs2(1,1);
	pos[n+1]=-1; t[n+1].fa=n+2;
	pos[n+2]=n+2; t[n+2].son[0]=n+1; root=n+2;
	rep(i,1,n) ins(i),v[i]=true;
	for (int T=read(),opt;T--;) {
		for (opt=getchar();opt!='G'&&opt!='C';opt=getchar()) ;
		if (opt=='C') {
			int x=read();
			if (v[x]) del(x),tot--;
			v[x]^=1;
			if (v[x]) ins(x),tot++;
		} else {
			if (tot==0) puts("-1");
			else if (tot==1) puts("0");
			else printf("%d\n", t[root].p.len);
		}
	}
	return 0;
}

bzoj1095 [ZJOI2007]Hide 捉迷藏線段樹DescriptionSolutionupdateCode

Description

Solution

update

Code

繼續閱讀

C語言第四章自述2第四章選擇結構程式設計

面試題:vector和map的差別，異同。空間分布，100萬資料存哪個比較合适。一、疊代器差別二、vector三、Map、Set四、vector_map 為什麼比map效率高五、如何選擇六、容器選擇原則七、效率對比

C++ 多線程用條件變量确定線程的執行順序而不是使用 sleep(1)

POJ 1284 Primitive Roots (歐拉函數&原根定理)

CQ V1.0分詞bates(基于雙數組tire樹)—應該是目前最快的中文分詞算法

成員函數初始化清單

2021-08-13c++——類之操作符重載

swmm與lisflood-fp源碼如何一起編譯 CMake指令

Windows下VS開發環境環境安裝工程項目設定關于Debug和Release的提示

一文看懂字元串的加減乘除

C++ 第十五周報告1--《冒泡法排序》

C++實作簡單順序表

C經典書籍筆記——C陷阱與缺陷②(文法陷阱之優先級)一、錯誤案列二、優先級規律

線性表之順序表的實作

C++判斷素數、求最大公約數代碼判斷一個數是否為素數求兩個數的最大公約數

SequoiaDB巨杉資料庫C++驅動概述

bzoj1095 [ZJOI2007]Hide 捉迷藏 線段樹DescriptionSolutionupdateCode

Description

Solution

update

Code

繼續閱讀

bzoj1095 [ZJOI2007]Hide 捉迷藏線段樹DescriptionSolutionupdateCode