差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 2020-2021:teams:legal_string:jxm2001:点分树 [2020/06/13 15:20]
jxm2001
+++ 2020-2021:teams:legal_string:jxm2001:点分树 [2020/07/27 22:54] (当前版本)
jxm2001 ↷ 页面2020-2021:teams:legal_string:点分树被移动至2020-2021:teams:legal_string:jxm2001:点分树
@@ 行 7: / 行 7: @@
 特别适用于一些需要维护与路径长度相关信息的题目。
-一般空间复杂度为 $O(n\log n)$，单次查询或修改时间复杂度为 $O\left(\log^2 n\right)$。
+一般空间复杂度为 $O(n\log n)$，单次查询或修改时间复杂度为 $O\left(\log^2 n\right)$，**常数极大，慎用。**
-===== 算法思想 ====
+===== 算法思想 =====
 把点分治过程中得到的重心连接，得到一棵虚树，该树有如下性质：
@@ 行 43: / 行 43: @@
 给出一棵 $n$ 个结点的点权树，相邻点距离为 $1$ ，接下来 $m$ 个操作，操作有以下两种：
-操作0：输出所有到结点 $x$ 距离不超过 $k$。
+操作0：输出所有到结点 $x$ 距离不超过 $k$ 的结点的点权和。
 操作1：将结点 $x$ 点权修改为 $y$。
@@ 行 79: / 行 79: @@
 <hidden 查看代码>
 <code cpp>
-#include <iostream>
-#include <cstdio>
-#include <algorithm>
-#include <cstring>
-#include <cctype>
-#include <vector>
-#define _for(i,a,b) for(int i=(a);i<(b);++i)
-#define _rep(i,a,b) for(int i=(a);i<=(b);++i)
-using namespace std;
-typedef long long LL;
-inline int read_int(){
-	int t=0;bool sign=false;char c=getchar();
-	while(!isdigit(c)){sign|=c=='-';c=getchar();}
-	while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();}
-	return sign?-t:t;
-}
-inline void write(LL x){
-	register char c[21],len=0;
-	if(!x)return putchar('0'),void();
-	if(x<0)x=-x,putchar('-');
-	while(x)c[++len]=x%10,x/=10;
-	while(len)putchar(c[len--]+48);
-}
-inline void enter(LL x){write(x),putchar('\n');}
 const int MAXN=1e5+5,MAXM=20,inf=1e6+5;
 struct Edge{
@@ 行 281: / 行 257: @@
 操作2：询问树上距离最远的黑色点对的距离，如果只有一个黑点输出 $0$ ，如果没有黑点输出 $-1$。
-**题解**
+**题解1**
 考虑对每个结点 $x$ ，建立两个大根堆，第一个堆维护每棵在虚树中属于结点 $x$ 的子树到结点 $x$ 的最大距离。
@@ 行 305: / 行 281: @@
 <hidden 查看代码>
 <code cpp>
-#include <iostream>
-#include <cstdio>
-#include <queue>
-#include <algorithm>
-#include <cstring>
-#include <cctype>
-#include <vector>
-#define _for(i,a,b) for(int i=(a);i<(b);++i)
-#define _rep(i,a,b) for(int i=(a);i<=(b);++i)
-#define mem(a,b) memset(a,b,sizeof(a))
-using namespace std;
-typedef long long LL;
-inline int read_int(){
-	int t=0;bool sign=false;char c=getchar();
-	while(!isdigit(c)){sign|=c=='-';c=getchar();}
-	while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();}
-	return sign?-t:t;
-}
-inline void write(LL x){
-	register char c[21],len=0;
-	if(!x)return putchar('0'),void();
-	if(x<0)x=-x,putchar('-');
-	while(x)c[++len]=x%10,x/=10;
-	while(len)putchar(c[len--]+48);
-}
-inline char get_char(){
-	char c=getchar();
-	while(c==' '||c=='\n'||c=='\r')c=getchar();
-	return c;
-}
-inline void enter(LL x){write(x),putchar('\n');}
 const int MAXN=1e5+5,MAXM=20,inf=1e6+5;
 struct Edge{
@@ 行 351: / 行 296: @@
 struct Heap{
 	priority_queue<int> q1,q2;
-	void debug(){
-		enter(q1.size()-q2.size());
-	}
 	void Insert(int x){
 		q1.push(x);
@@ 行 517: / 行 459: @@
 </hidden>
+**题解2**
+这个解法和点分树没什么关系，用的是括号序列加线段树，时空间复杂度都比点分树少一个 $\log$。
+这里仅提供代码，有兴趣的可以自行学习。
+<hidden 查看代码>
+<code cpp>
+const int MAXN=1e5+5,MAXN_2=3e5+5,inf=1e6+5;
+struct Edge{
+	int to,next;
+}edge[MAXN<<1];
+int n,q,edge_cnt,head[MAXN],p[MAXN],a[MAXN_2],dfs_t;
+inline void Insert(int u,int v){
+	edge[++edge_cnt].to=v;
+	edge[edge_cnt].next=head[u];
+	head[u]=edge_cnt;
+}
+struct Node{
+	int l,r;
+	int lc,rc,ans,l1,l2,r1,r2;
+	void build(int x){
+		if(x==1)
+		lc=rc=l1=l2=r1=r2=ans=0;
+		else{
+			if(!x)
+			lc=rc=0;
+			else if(x==-1)
+			lc=1;
+			else
+			rc=1;
+			ans=l1=l2=r1=r2=-inf;
+		}
+	}
+}node[MAXN_2<<2];
+inline void push_up(int k){
+	int l=k<<1,r=k<<1|1;
+	node[k].lc=node[l].lc+max(node[r].lc-node[l].rc,0);
+	node[k].rc=node[r].rc+max(node[l].rc-node[r].lc,0);
+	node[k].ans=max(max(node[l].ans,node[r].ans),max(node[l].r1+node[r].l2,node[l].r2+node[r].l1));
+	node[k].l1=max(node[l].l1,max(node[l].lc-node[l].rc+node[r].l1,node[l].lc+node[l].rc+node[r].l2));
+	node[k].l2=max(node[l].l2,node[l].rc-node[l].lc+node[r].l2);
+	node[k].r1=max(node[r].r1,max(node[l].r1+node[r].rc-node[r].lc,node[l].r2+node[r].lc+node[r].rc));
+	node[k].r2=max(node[r].r2,node[l].r2+node[r].lc-node[r].rc);
+}
+void build(int k,int lef,int rig){
+	node[k].l=lef,node[k].r=rig;
+	int mid=lef+rig>>1;
+	if(lef==rig){
+		node[k].build(a[mid]);
+		return;
+	}
+	build(k<<1,lef,mid);
+	build(k<<1|1,mid+1,rig);
+	push_up(k);
+}
+void update(int k,int pos){
+	if(node[k].l==node[k].r){
+		node[k].build(a[pos]);
+		return;
+	}
+	int mid=node[k].l+node[k].r>>1;
+	if(mid<pos)
+	update(k<<1|1,pos);
+	else
+	update(k<<1,pos);
+	push_up(k);
+}
+void dfs(int u,int fa){
+	a[++dfs_t]=-2;
+	p[u]=++dfs_t;
+	a[dfs_t]=1;
+	for(int i=head[u];i;i=edge[i].next){
+		int v=edge[i].to;
+		if(v==fa)
+		continue;
+		dfs(v,u);
+	}
+	a[++dfs_t]=-1;
+}
+int main()
+{
+	n=read_int();
+	int u,v;
+	_for(i,1,n){
+		u=read_int(),v=read_int();
+		Insert(u,v);
+		Insert(v,u);
+	}
+	dfs(1,0);
+	build(1,1,dfs_t);
+	q=read_int();
+	char opt;
+	int x;
+	while(q--){
+		opt=get_char();
+		if(opt=='G'){
+			if(n>1)
+			enter(node[1].ans);
+			else if(n==1)
+			puts("0");
+			else
+			puts("-1");
+		}
+		else{
+			x=read_int();
+			if(a[p[x]])
+			n--;
+			else
+			n++;
+			a[p[x]]^=1;
+			update(1,p[x]);
+		}
+	}
+	return 0;
+}
+</code>
+</hidden>

CVBB ACM Team

用户工具

站点工具

差别

页面工具