牛客周赛 Round 32 D 题

小红的二进制数

D题链接

题目大意 一个01串从第i个位置出发到第j个位置结尾且第j个位置为1的路径条数,只能从父亲走到儿子

输入 1.n(1<=n<=1e5) 2.长度为n的01串 3.n-1条边

分析:树形dp或者说dfs，O(n)的复杂度

#include<bits/stdc++.h>
using namespace std;

int n;
string s;
int dp[100100];
vector<int>g[100100];

void dfs(int x,int fa){
	dp[x] = s[x]-'0';
	for(auto i :g[x]){
		if(i==fa) continue;
		dfs(i,x);
		dp[x]+=dp[i];
	}
}

int main(){
	cin>>n>>s;
	s='0'+s;
	for(int i = 1;i<n;++i){
		int x,y;
		cin>>x>>y;
		g[x].push_back(y);
		g[y].push_back(x);
	}
	dfs(1,0);
	for(int i = 1;i<=n;++i) cout<<dp[i]-(s[i]-'0')<<"\n";	
	return 0;
}