Submission #1221430

#	Time	Username	Problem	Language	Result	Execution time	Memory
1221430		boclobanchat	Power Plant (JOI20_power)	C++20	100 / 100	121 ms	30140 KiB

power

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

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