Submission #1221430

#TimeUsernameProblemLanguageResultExecution timeMemory
1221430boclobanchatPower Plant (JOI20_power)C++20
100 / 100
121 ms30140 KiB
#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e5+5;
vector<int> ds[MAXN];
int dp[MAXN][3],F[MAXN][3];
string s;
void dfs(int i,int pre)
{
	for(auto v:ds[i]) if(v!=pre)
	{
		dfs(v,i);
		F[i][2]=max(F[i][2],F[i][1])+dp[v][1];
		F[i][1]=max(F[i][1],dp[v][1]);
	}
	dp[i][1]=max(F[i][0]+(s[i]=='1'),max(F[i][1],F[i][2])-(s[i]=='1'));
	dp[i][2]=max(F[i][2]-(s[i]=='1'),max(F[i][1],F[i][0])+(s[i]=='1'));
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin>>n;
    for(int i=1;i<n;i++)
    {
    	int l,r;
    	cin>>l>>r;
    	ds[l].push_back(r),ds[r].push_back(l);
	}
	cin>>s;
	s=' '+s;
	dfs(1,1);
	int ans=0;
	for(int i=1;i<=n;i++) ans=max(ans,dp[i][2]);
	cout<<ans;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...