Submission #891383

#	Time	Username	Problem	Language	Result	Execution time	Memory
891383		amirhoseinfar1385	Power Plant (JOI20_power)	C++17	100 / 100	94 ms	29292 KiB

power

#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";
}

• Subtask 1: 6 / 6
• Subtask 2: 41 / 41
• Subtask 3: 53 / 53