CVBB ACM Team

到此差别页面的链接

--- 2020-2021:teams:legal_string:jxm2001:树上启发式合并 [2020/07/26 11:29]
jxm2001
+++ 2020-2021:teams:legal_string:jxm2001:树上启发式合并 [2020/07/28 20:31] (当前版本)
jxm2001
@@ 行 3: / 行 3: @@
 ===== 算法简介 =====
-可离线处理子树相关信息统计的算法，时间复杂度 $O(n\log n)$，空间复杂度 $O(n)$。
+一种离线处理子树相关信息统计的算法，时间复杂度 $O(n\log n)$，空间复杂度 $O(n)$。
 ===== 算法思想 =====
@@ 行 9: / 行 9: @@
 首先发现对每棵子树进行信息统计时，只需要合并所有儿子节点所在子树信息，最后加上该节点本身信息即可。
-考虑信息合并的过程，类比并查集的启发式合并，发现把节点数少的子树信息合并到节点数多的子树将得到更优复杂度。
+考虑优化信息合并的过程，类比并查集的启发式合并。
+显然把节点数少的子树信息合并到节点数多的子树将得到更优复杂度。
 于是考虑保留重儿子子树的统计信息，然后暴力遍历轻儿子子树，合并结果。
@@ 行 32: / 行 34: @@
 ==== 题解 ====
+考虑字符串排序后能构成回文串的条件，发现只要出现字符串中出现奇数次的字符不超过一种就行。
+于是只需要维护每个节点子树的每个深度的每种字符个数就行了。
+ps. 字母总共就 $26$ 种，考虑状压异或，然后根据 $dfs$ 序建立 $n$ 棵线段树维护深度为 $1\sim n$ 的节点可以实现在线查找。
+<hidden 查看代码>
+<code cpp>
+const int MAXN=5e5+5;
+struct Edge{
+	int to,next;
+}edge[MAXN<<1];
+int head[MAXN],edge_cnt;
+void Insert(int u,int v){
+	edge[++edge_cnt].to=v;
+	edge[edge_cnt].next=head[u];
+	head[u]=edge_cnt;
+}
+char buf[MAXN];
+int cnt[MAXN][30];
+bool ans[MAXN];
+vector<pair<int,int> > query[MAXN];
+bool check(int d){
+	int temp=0;
+	_for(i,0,26)temp+=cnt[d][i]&1;
+	return temp<=1;
+}
+int d[MAXN],sz[MAXN],dfs_id[MAXN],node_id[MAXN],dfs_t;
+int h_son[MAXN],mson[MAXN];
+void dfs_1(int u,int depth){
+	sz[u]=1;d[u]=depth;dfs_id[u]=++dfs_t;node_id[dfs_t]=u;mson[u]=0;
+	for(int i=head[u];i;i=edge[i].next){
+		int v=edge[i].to;
+		dfs_1(v,depth+1);
+		sz[u]+=sz[v];
+		if(sz[v]>mson[u]){
+			h_son[u]=v;
+			mson[u]=sz[v];
+		}
+	}
+}
+void update_node(int u,int v){cnt[d[u]][buf[u]-'a']+=v;}
+void update_tree(int u,int v){
+	_for(i,0,sz[u])
+	update_node(node_id[dfs_id[u]+i],v);
+}
+void dfs_2(int u,bool del){
+	for(int i=head[u];i;i=edge[i].next){
+		int v=edge[i].to;
+		if(v==h_son[u])continue;
+		dfs_2(v,true);
+	}
+	if(h_son[u])dfs_2(h_son[u],false);
+	update_node(u,1);
+	for(int i=head[u];i;i=edge[i].next){
+		int v=edge[i].to;
+		if(v==h_son[u])continue;
+		update_tree(v,1);
+	}
+	_for(i,0,query[u].size())
+	ans[query[u][i].first]=check(query[u][i].second);
+	if(del)update_tree(u,-1);
+}
+int main()
+{
+	int n=read_int(),q=read_int(),root=1,u,d;
+	_rep(i,2,n)
+	Insert(read_int(),i);
+	scanf("%s",buf+1);
+	_for(i,0,q){
+		u=read_int(),d=read_int();
+		query[u].push_back(make_pair(i,d));
+	}
+	dfs_1(root,root);
+	dfs_2(root,false);
+	_for(i,0,q){
+		if(ans[i])
+		puts("Yes");
+		else
+		puts("No");
+	}
+	return 0;
+}
+</code>
+</hidden>
+===== 算法练习 =====
+==== 习题一 ====
+[[https://www.luogu.com.cn/problem/CF600E|CF600E]]
+=== 题意 ===
+给定一个以 $1$ 为根的 $n$ 个节点的树，每个结点都有一种颜色。
+求每个节点所在子树种数量最多的颜色(如果有多个满足条件的颜色则将所有颜色编号相加)。
+=== 题解 ===
+题目难度不高，这里仅给出代码供参考。
+<hidden 查看代码>
+<code cpp>
+const int MAXN=1e5+5;
+struct Edge{
+	int to,next;
+}edge[MAXN<<1];
+int head[MAXN],edge_cnt;
+void Insert(int u,int v){
+	edge[++edge_cnt].to=v;
+	edge[edge_cnt].next=head[u];
+	head[u]=edge_cnt;
+}
+int color[MAXN],cnt[MAXN],max_c;LL sum_c,ans[MAXN];
+int sz[MAXN],dfs_id[MAXN],node_id[MAXN],dfs_t;
+int h_son[MAXN],mson[MAXN];
+void dfs_1(int u,int fa){
+	sz[u]=1;dfs_id[u]=++dfs_t;node_id[dfs_t]=u;mson[u]=0;
+	for(int i=head[u];i;i=edge[i].next){
+		int v=edge[i].to;
+		if(v==fa)continue;
+		dfs_1(v,u);
+		sz[u]+=sz[v];
+		if(sz[v]>mson[u]){
+			h_son[u]=v;
+			mson[u]=sz[v];
+		}
+	}
+}
+void add_node(int u){
+	cnt[color[u]]++;
+	if(cnt[color[u]]>max_c)
+	max_c=cnt[color[u]],sum_c=color[u];
+	else if(cnt[color[u]]==max_c)
+	sum_c+=color[u];
+}
+void add_tree(int u){
+	_for(i,0,sz[u])
+	add_node(node_id[dfs_id[u]+i]);
+}
+void del_tree(int u){
+	_for(i,0,sz[u])
+	cnt[color[node_id[dfs_id[u]+i]]]--;
+}
+void dfs_2(int u,int fa,bool del){
+	for(int i=head[u];i;i=edge[i].next){
+		int v=edge[i].to;
+		if(v==h_son[u]||v==fa)continue;
+		dfs_2(v,u,true);
+	}
+	if(h_son[u])dfs_2(h_son[u],u,false);
+	add_node(u);
+	for(int i=head[u];i;i=edge[i].next){
+		int v=edge[i].to;
+		if(v==h_son[u]||v==fa)continue;
+		add_tree(v);
+	}
+	ans[u]=sum_c;
+	if(del)max_c=sum_c=0,del_tree(u);
+}
+int main()
+{
+	int n=read_int(),root=1,u,v;
+	_rep(i,1,n)
+	color[i]=read_int();
+	_for(i,1,n){
+		u=read_int();
+		v=read_int();
+		Insert(u,v);Insert(v,u);
+	}
+	dfs_1(root,0);
+	dfs_2(root,0,false);
+	_rep(i,1,n)
+	space(ans[i]);
+	return 0;
+}
+</code>
+</hidden>
+==== 习题二 ====
+[[https://www.luogu.com.cn/problem/CF1009F|CF1009F]]
+=== 题意 ===
+给定一个以 $1$ 为根的 $n$ 个节点的树，定义 $d(u,x)$ 为 $u$ 的子树中到 $u$ 距离为 $x$ 的节点数。
+对于每个点，求一个最小的 $k$，使得 $d(u,k)$ 最大。
+=== 题解 ===
+题目难度不高，这里仅给出代码供参考。
+<hidden 查看代码>
+<code cpp>
+const int MAXN=1e6+5;
+struct Edge{
+	int to,next;
+}edge[MAXN<<1];
+int head[MAXN],edge_cnt;
+void Insert(int u,int v){
+	edge[++edge_cnt].to=v;
+	edge[edge_cnt].next=head[u];
+	head[u]=edge_cnt;
+}
+int color[MAXN],cnt[MAXN],max_c,ans_d,ans[MAXN];
+int d[MAXN],sz[MAXN],dfs_id[MAXN],node_id[MAXN],dfs_t;
+int h_son[MAXN],mson[MAXN];
+void dfs_1(int u,int fa,int depth){
+	d[u]=depth;sz[u]=1;dfs_id[u]=++dfs_t;node_id[dfs_t]=u;mson[u]=0;
+	for(int i=head[u];i;i=edge[i].next){
+		int v=edge[i].to;
+		if(v==fa)continue;
+		dfs_1(v,u,depth+1);
+		sz[u]+=sz[v];
+		if(sz[v]>mson[u]){
+			h_son[u]=v;
+			mson[u]=sz[v];
+		}
+	}
+}
+void add_node(int u){
+	cnt[d[u]]++;
+	if(cnt[d[u]]>max_c||(cnt[d[u]]==max_c&&d[u]<ans_d))
+	max_c=cnt[d[u]],ans_d=d[u];
+}
+void add_tree(int u){
+	_for(i,0,sz[u])
+	add_node(node_id[dfs_id[u]+i]);
+}
+void del_tree(int u){
+	_for(i,0,sz[u])
+	cnt[d[node_id[dfs_id[u]+i]]]--;
+}
+void dfs_2(int u,int fa,bool del){
+	for(int i=head[u];i;i=edge[i].next){
+		int v=edge[i].to;
+		if(v==h_son[u]||v==fa)continue;
+		dfs_2(v,u,true);
+	}
+	if(h_son[u])dfs_2(h_son[u],u,false);
+	add_node(u);
+	for(int i=head[u];i;i=edge[i].next){
+		int v=edge[i].to;
+		if(v==h_son[u]||v==fa)continue;
+		add_tree(v);
+	}
+	ans[u]=ans_d-d[u];
+	if(del)max_c=0,ans_d=-1,del_tree(u);
+}
+int main()
+{
+	int n=read_int(),root=1,u,v;
+	_for(i,1,n){
+		u=read_int();
+		v=read_int();
+		Insert(u,v);Insert(v,u);
+	}
+	dfs_1(root,0,0);
+	dfs_2(root,0,false);
+	_rep(i,1,n)
+	enter(ans[i]);
+	return 0;
+}
+</code>
+</hidden>
+==== 习题三 ====
+[[https://www.luogu.com.cn/problem/CF741D|CF741D]]
+=== 题意 ===
+给定一个以 $1$ 为根的 $n$ 个节点的树，树上每条边代表一个英文小写字母($a\sim v$)。对于每个点，求其子树中的最长回文路径。
+=== 题解 ===
+显然树上启发式合并不能直接统计路径，想办法把路径转化为点权。
+考虑状压异或，令每个节点点权为根节点到该节点的路径的字母的异或和。
+则任意两点间路径构成回文串等价于这两点点权异或为 $0$ 或者恰为 $2$ 的幂次。
+对每个结点的答案，先考虑经过根节点的路径贡献，可以使用桶记录每个点权出现的最大深度，利用深度可以得到路径长度。
+对与子树中的路径，可以从子树向上合并答案。
+时间复杂度 $O(cn\log n)$，空间复杂度 $O(2^c)$，其中 $c$ 为字母种类数。
+<hidden 查看代码>
+<code cpp>
+const int MAXN=5e5+5,MAXS=22;
+struct Edge{
+	int to,w,next;
+}edge[MAXN];
+int head[MAXN],edge_cnt;
+void Insert(int u,int v,int w){
+	edge[++edge_cnt]=Edge{v,w,head[u]};
+	head[u]=edge_cnt;
+}
+int c[1<<MAXS],ans[MAXN];
+int d[MAXN],sz[MAXN],w[MAXN],dfs_id[MAXN],node_id[MAXN],dfs_t;
+int h_son[MAXN],mson[MAXN];
+void dfs_1(int u){
+	sz[u]=1;dfs_id[u]=++dfs_t;node_id[dfs_t]=u;mson[u]=0;
+	for(int i=head[u];i;i=edge[i].next){
+		int v=edge[i].to;
+		w[v]=w[u]^edge[i].w;
+		d[v]=d[u]+1;
+		dfs_1(v);
+		sz[u]+=sz[v];
+		if(sz[v]>mson[u]){
+			h_son[u]=v;
+			mson[u]=sz[v];
+		}
+	}
+}
+int query_node(int u){
+	int ans=c[w[u]]+d[u];
+	_for(i,0,MAXS){
+		if(c[w[u]^(1<<i)]+d[u]>ans)
+		ans=c[w[u]^(1<<i)]+d[u];
+	}
+	return ans;
+}
+void add_node(int u){c[w[u]]=max(c[w[u]],d[u]);}
+int add_tree(int u){
+	int ans=0;
+	_for(i,0,sz[u])
+	ans=max(ans,query_node(node_id[dfs_id[u]+i]));
+	_for(i,0,sz[u])
+	add_node(node_id[dfs_id[u]+i]);
+	return ans;
+}
+void del_node(int u){c[w[u]]=-MAXN;}
+void del_tree(int u){
+	_for(i,0,sz[u])
+	del_node(node_id[dfs_id[u]+i]);
+}
+void dfs_2(int u,bool del){
+	ans[u]=d[u]*2;
+	for(int i=head[u];i;i=edge[i].next){
+		int v=edge[i].to;
+		if(v==h_son[u])continue;
+		dfs_2(v,true);
+	}
+	if(h_son[u])dfs_2(h_son[u],false);
+	ans[u]=max(ans[u],query_node(u));
+	c[w[u]]=max(c[w[u]],d[u]);
+	for(int i=head[u];i;i=edge[i].next){
+		int v=edge[i].to;
+		if(v==h_son[u])continue;
+		ans[u]=max(ans[u],add_tree(v));
+	}
+	ans[u]-=d[u]*2;
+	for(int i=head[u];i;i=edge[i].next)
+	ans[u]=max(ans[u],ans[edge[i].to]);
+	if(del)del_tree(u);
+}
+int main()
+{
+	int n=read_int(),root=1,f;char cc;
+	_for(i,0,1<<MAXS)
+	c[i]=-MAXN;
+	_rep(i,2,n){
+		f=read_int();
+		cc=get_char();
+		Insert(f,i,1<<(cc-'a'));
+	}
+	w[root]=0;d[root]=0;
+	dfs_1(root);
+	dfs_2(root,false);
+	_rep(i,1,n)
+	space(ans[i]);
+	return 0;
+}
+</code>
+</hidden>

CVBB ACM Team

用户工具

站点工具

页面工具