专栏文章

P12195

XXuan_tmp
P12195题解参与者 2已保存评论 3

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
3 条
当前快照
1 份
快照标识符
@miplbha5
此快照首次捕获于
2025/12/03 13:52
3 个月前
此快照最后确认于
2025/12/03 13:52
3 个月前
查看原文

题目大意

给定一棵 nn 个点的树和一个点的序列 ss，要求按顺序访问序列中的所有点，并且树上每条边要被访问恰好 22 次。问每个点是否能作为起点。

sol

首先指定 11 为树根，把所有 si→si+1(1≤i<m)s_i\to s_{i+1}(1\le i < m) 的路径取出，构成一个极小联通块。我们发现不管怎么走，在事件 ii 和 i+1i+1 发生之间，si→si+1s_i\to s_{i+1} 的最短路径上的边一定都会被访问至少一次，于是我们可以通过树剖计算出每条边至少要被访问几次。如果有任何一条边被访问了 ≥3\ge 3 次，那么从任何一个点开始都无法成功构成一个巡游。
然后我们把选择的起点加上，也就是 S→s1S\to s_1 的最短路径上所有边都会至少被访问 11 次。很容易发现如果要满足每条边访问不超过 22 次，那么 SS 只能从能被 s1s_1 通过最少访问次数为 0,10,1 的边遍历到的联通块中选取。
接下来我们来证明此时这个联通块中所有点都能作为起始点。
我们取出 S→s1,s1→s2,…,sm−1→smS\to s_1,s_1\to s_2,\dots,s_{m-1}\to s_m 这 mm 条路径所构成的联通块，则这个联通块上每条边的最少访问次数均为 11 或 22，每个点都至少被遍历了一次。
联通块内每个点 uu 第一次遍历到时，都将其不在联通块内的子树全部遍历完成，容易知道这是可行的。而在联通块内，取出 S→s1,s1→s2,…,sm−1→sm,sm→SS\to s_1,s_1\to s_2,\dots,s_{m-1}\to s_m,s_m\to S 这 m+1m+1 条路径，容易发现这构成了一个 dfs 序。所以只需要按照这个顺序进行遍历，并在遍历到一个点时处理好其所有不在联通块内的子树即可。
所以只需要：
  • 树剖计算出每条边至少要被访问几次。
  • 找到能被 s1s_1 通过最少访问次数为 0,10,1 的边遍历到的联通块。
答案就是联通块的大小。

code

CPP
#include<bits/stdc++.h>
using namespace std;
#define int long long
vector<int>G[200005];
vector<pair<int,int> >E[200005];
struct node{
	int len,w,lz;
}tr[800005];
int n,m,cnt,a[200005],b[200005];
int dis[200005],fa[200005],son[200005],siz[200005],tp[200005],idx[200005],ans[200005];
void dfs1(int u,int f){
	dis[u]=dis[f]+1;
	fa[u]=f,siz[u]=1;
	for(int i=0;i<G[u].size();i++){
		int v=G[u][i];
		if(v==f) continue;
		dfs1(v,u);siz[u]+=siz[v];
		if(siz[v]>siz[son[u]])son[u]=v;
	}
}
void pushup(int x){
	tr[x].w=tr[x<<1].w+tr[x<<1|1].w;
}
void Build(int x,int l,int r){
	tr[x].len=r-l+1;
	if(l==r)return;
	int mid=(l+r)>>1;
	Build(x<<1,l,mid);
	Build(x<<1|1,mid+1,r);
	pushup(x);
}
void dfs2(int u,int top){
	idx[u]=++cnt;
	a[cnt]=b[u];
	tp[u]=top;
	if(!son[u]) return ;
	dfs2(son[u],top);
	for(int i=0;i<G[u].size();i++){
		int v=G[u][i];
		if(idx[v])continue;
		dfs2(v,v);
	}
}
void pushdown(int x){
	if(!tr[x].lz) return ;
	tr[x<<1].w=(tr[x<<1].w+tr[x<<1].len*tr[x].lz);
	tr[x<<1|1].w=(tr[x<<1|1].w+tr[x<<1|1].len*tr[x].lz);
	tr[x<<1].lz=(tr[x<<1].lz+tr[x].lz);
	tr[x<<1|1].lz=(tr[x<<1|1].lz+tr[x].lz);
	tr[x].lz=0;
}
void upd(int x,int l,int r,int L,int R,int val){
	if(R<L)return;
	if(L<=l&&r<=R){
		tr[x].w+=tr[x].len*val;
		tr[x].lz+=val;
		return ;
	}
	pushdown(x);
	int mid=(l+r)>>1;
	if(L<=mid)upd(x<<1,l,mid,L,R,val);
	if(R>mid)upd(x<<1|1,mid+1,r,L,R,val);
	pushup(x);
}
void TreeAdd(int x,int y){
	while(tp[x]!=tp[y]){
		if(dis[tp[x]]<dis[tp[y]]) swap(x,y);
		upd(1,1,n,idx[tp[x]],idx[x],1);
		x=fa[tp[x]];
	}
	if(dis[x]>dis[y]) swap(x,y);
	upd(1,1,n,idx[x]+1,idx[y],1);
}
void dfs(int u,int f){
	ans[u]=1;
	for(int i=0;i<E[u].size();i++){
		int v=E[u][i].first,w=E[u][i].second;
		if(v==f||w>1)continue;
		dfs(v,u);
	}
}
int query(int x,int l,int r,int ps){
	if(l==r)return tr[x].w;
	pushdown(x);
	int mid=(l+r)>>1,ans=0;
	if(ps<=mid)return query(x<<1,l,mid,ps);
	else return query(x<<1|1,mid+1,r,ps);
}
signed main(){
	cin>>n>>m;
	for(int i=1;i<n;i++){
		int u,v;cin>>u>>v;
		G[u].push_back(v);
		G[v].push_back(u);
	}
	dfs1(1,0);
	dfs2(1,1);
	Build(1,1,n);
	cin>>b[1];
	for(int i=2;i<=m;i++){
		cin>>b[i];
		TreeAdd(b[i-1],b[i]);
	}
	for(int i=2;i<=n;i++){
		int w=query(1,1,n,idx[i]);
		if(w>2){
			for(int i=1;i<=n;i++)cout<<"0\n";
			return 0;
		}
		E[fa[i]].push_back({i,w});
		E[i].push_back({fa[i],w});
	}
	dfs(b[1],-1);
	for(int i=1;i<=n;i++)cout<<ans[i]<<'\n';
	return 0;
}

评论

共 3 条评论，欢迎与作者交流。

正在加载评论...