树上问题1——树的遍历

例题

1. Power Strip（洛谷B3681）

题面

解析

一道简单的线性（树形）DP。

代码

# include<iostream>
using namespace std;

const int N=1e6+5;
int n,u[N];
long long a[N],f[N];
bool vis[N];

int main(){
	cin>>n;
	for(int i=2;i<=n;++i) cin>>u[i];
	for(int i=1;i<=n;++i){
		cin>>a[i];
		f[i]=a[i];
	}
	for(int i=n;i>=2;--i) f[u[i]]+=f[i];
	for(int i=1;i<=n;++i) cout<<f[i]<<" ";
	return 0;
}

2. DFS Order（洛谷P9872）

题面

给定一棵以 $1$ 为根节点的树，若从根节点开始按任意顺序进行深度优先搜索，则第 $i$ 个点最小是第几个被搜到的？最大是第几个？

解析

代码

# include<iostream>
# include<vector>
using namespace std;

const int N=1e5+5;
int t,n,x,y;
int dep[N],sn[N];//深度，子节点数 
vector<int> son[N];

void dfs(int u){
	for(int i=0,l=son[u].size();i<l;++i){
		int v=son[u][i];
		dep[v]=dep[u]+1;
		dfs(v);
		sn[u]+=sn[v]+1;
	}
}

void solve(){
	cin>>n;
	for(int i=1;i<=n;++i){
		dep[i]=sn[i]=0;
		son[i].clear();
	}
	for(int i=1;i<=n-1;++i){
		cin>>x>>y;
		son[x].push_back(y);
	}
	dfs(1);
	for(int i=1;i<=n;++i)
		cout<<dep[i]+1<<" "<<n-sn[i]<<endl;
}

int main(){
	cin>>t;
	while(t--) solve();
	return 0;
}

3. Chino的树学（洛谷P5551）

题面

解析

代码

4. [CSP-S 2019 T2] 括号树（洛谷P5658）

题面

有一棵以 $1$ 号结点为根的有 $n$ 个结点的树，每个结点上恰有一个括号，可能是( 或)。

定义 $s_i$ 为：将根结点到 $i$ 号结点的简单路径上的括号，按结点经过顺序依次排列组成的括号串。记 $s_i$ 中的互不相同的且为合法括号串的子串数量为 $k_i$，输出 $i \times k_i$ 的异或和。

解析

一道简单的线性（树形）DP，注意细节。

代码

# include<iostream>
using namespace std;

const int N=5e5+5;
int n,fa[N],id[N];//节点i匹配到的最近的左括号节点编号
char s[N];
long long f1[N],f2[N],ans;

void find_id(int u){
	if(u==1) return;
	if(s[u]==')'){
		if(s[fa[u]]=='(') id[u]=fa[u];
		else{
			int t=fa[u];
			while(t){
				if(s[fa[id[t]]]=='('){
					id[u]=fa[id[t]];
					break;
				}
				t=fa[id[t]];
			}
		}
	}
}

int main(){
	cin>>n;
	for(int i=1;i<=n;++i) cin>>s[i];
	for(int i=2;i<=n;++i)
		cin>>fa[i];
	for(int i=1;i<=n;++i){
		find_id(i);
		if(id[i]){
			f1[i]=1;
			if(s[fa[id[i]]]==')')
				f1[i]+=f1[fa[id[i]]];
		}
		f2[i]=f2[fa[i]]+f1[i];
	}
	for(int i=1;i<=n;++i)
		ans=ans^(i*f2[i]);
	cout<<ans;
	return 0;
}

作业