제출 #891383

#제출 시각아이디문제언어결과실행 시간메모리
891383amirhoseinfar1385Power Plant (JOI20_power)C++17
100 / 100
94 ms29292 KiB
#include<bits/stdc++.h>
using namespace std;
const int maxn=200000+10;
int dp[maxn],res=0,n,val[maxn];
vector<int>adj[maxn];

void dfs(int u=1,int par=0){
	for(auto x:adj[u]){
		if(x!=par){
			dfs(x,u);
			dp[u]+=dp[x];
			res=max(res,dp[x]+val[u]);
		}
	}
	dp[u]=max(dp[u]+val[u]*-1,val[u]);
	return ;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	for(int i=0;i<n-1;i++){
		int u,v;
		cin>>u>>v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	for(int i=1;i<=n;i++)
	{
		char c;
		cin>>c;
		val[i]=c-'0';
	}
	dfs(1);
	res=max(res,dp[1]);
	cout<<res<<"\n";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...