제출 #1365729

#제출 시각아이디문제언어결과실행 시간메모리
1365729ivazivaPower Plant (JOI20_power)C++20
47 / 100
1597 ms30028 KiB
#include <bits/stdc++.h>

using namespace std;

#define MAXN 200005
#define int long long 

int n;string state;
vector<int> adj[MAXN];
int dp[MAXN];int answer=0;
int parent[MAXN];

void dfs(int node,int pret)
{
	int children=0;parent[node]=pret;
	for (int sled:adj[node])
	{
		if (sled==pret) continue;
		dfs(sled,node);children+=dp[sled];
    }
    if (state[node-1]=='0') dp[node]=max(children,(long long)0);
    else dp[node]=max(children-1,(long long)1);
}

void calculate(int node,int pret)
{
    int children=0;
    for (int sled:adj[pret])
    {
		if (sled!=node) children+=dp[sled];
	}
	if (state[pret-1]=='0') dp[pret]=max(children,(long long)0);
	else dp[pret]=max(children-1,(long long)1);
	children=0;for (int sled:adj[node]) children+=dp[sled];
	if (state[node-1]=='0') dp[node]=max(children,(long long)0);
	else dp[node]=max(children-1,(long long)1);
	answer=max(answer,max(dp[node],(long long)2));
	for (int sled:adj[node])
	{
		if (sled!=pret) calculate(sled,node);
	}
	children=0;
	for (int sled:adj[node])
	{
		if (sled!=pret) children+=dp[sled];
	}
	if (state[node-1]=='0') dp[node]=max(children,(long long)0);
	else dp[node]=max(children-1,(long long)1);
	children=0;for (int sled:adj[pret]) children+=dp[sled];
	if (state[pret-1]=='0') dp[pret]=max(children,(long long)0);
	else dp[pret]=max(children-1,(long long)1);
}

int32_t main()
{
	cin>>n;for (int i=1;i<n;i++) {int u,v;cin>>u>>v;adj[u].push_back(v);adj[v].push_back(u);}
	cin>>state;int number=0;for (int node=0;node<n;node++) number+=(state[node]-'0');
	if (number<=2) {cout<<number<<endl;return 0;}
	dfs(1,0);answer=max(dp[1],(long long)2);
	for (int node:adj[1]) calculate(node,1);
	cout<<answer<<endl;return 0;
}
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…