Submission #293488

#	Time	Username	Problem	Language	Result	Execution time	Memory
293488		nandonathaniel	Power Plant (JOI20_power)	C++14	100 / 100	203 ms	25976 KiB

power

#include<bits/stdc++.h>
using namespace std;
const int MAXN=200005;

vector<int> adj[MAXN];
int lampu[MAXN],dp[MAXN],ans;

void dfs(int now,int par){
	int maxi=0;
	bool leaf=true;
	for(auto nxt : adj[now]){
		if(nxt==par)continue;
		leaf=false;
		dfs(nxt,now);
		dp[now]+=dp[nxt];
		maxi=max(maxi,dp[nxt]);
	}
	if(lampu[now]){
		dp[now]--;
		dp[now]=max(dp[now],1);
		if(!leaf)ans=max(ans,maxi+1);
	}
	ans=max(ans,dp[now]);
}

int main(){
	ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	int n,u,v;
	char a;
	cin >> n;
	for(int i=1;i<n;i++){
		cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	for(int i=1;i<=n;i++){
		cin >> a;
		if(a=='1')lampu[i]=1;
	}
	dfs(1,-1);
	cout << ans << '\n';
	return 0;
}

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