제출 #1326208

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

#define fst first
#define snd second
#define pb push_back
#define mset(a,v) memset(a,v,sizeof(a))
#define SZ(x) (int)x.size()
#define ALL(x) x.begin(),x.end()
#define forn(i,a,b) for(int i = a; i<b; i++)
#define FIN ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#ifdef D
	#define debug(x) cout << x
#else
	#define debug(x) //nothing
#endif

using namespace std;
typedef long long ll;

const int MAXN = 200000+5;

ll n;
vector<ll> adj[MAXN];

bool is[MAXN];
ll down[MAXN][3];
ll pa[MAXN];

ll f(ll nd , ll t, ll p){
	ll &res = down[nd][t];
	if(res!=-1) return res;
	pa[nd]=p;
	if(is[nd]){
		res=1;
	}else res=0;

	if(t==0){
		ll pres = 0;
		for(auto i:adj[nd]) if(i!=p){
			pres+=f(i,0,nd);
		}
		res=max(res,pres- (is[nd]?1:0));
	}else{
		ll best = 0;
		for(auto i:adj[nd]) if(i!=p){
			best=max(best,f(i,0,nd));
		}
		res=max(res,best+(is[nd]?1:0));
	}

	debug("lastf "<<nd<<" "<<p<<" "<<res<<'\n');
	return res;
}

ll up[MAXN][3];
ll dp[MAXN][3];

void newf(ll nd, ll t, ll p){
	ll &res = dp[nd][t];
	res=down[nd][0];
	res=max(res,down[nd][1]);

	up[nd][2]=(is[nd]?1:0);
	up[nd][1]=(is[nd]?1:0);
	up[nd][0]=-(is[nd]?1:0);

	if(p!=-1){
		ll pres = up[p][0]; for(auto i:adj[p]) if(i!=nd && (p==-1 || i!=pa[p])) pres+=down[i][0];

		up[nd][0]=max(up[nd][0],pres-(is[nd]?1:0)); up[nd][0]=max(up[nd][0],up[p][1]-(is[nd]?1:0));
		up[nd][1]=max(up[nd][1],pres-(is[nd]?1:0)); up[nd][1]=max(up[nd][1],up[p][1]-(is[nd]?1:0));
		up[nd][2]=max(up[nd][2],pres+(is[nd]?1:0)); up[nd][2]=max(up[nd][2],up[p][1]+(is[nd]?1:0));

		res=max(res, up[nd][2]);
	}

	debug("newup "<<nd<<" "<<up[nd][0]<<" "<<up[nd][1]<<" "<<up[nd][2]<<'\n');
	debug("newf "<<nd<<" "<<res<<'\n');

	for(auto i:adj[nd])if(i!=p){
		newf(i,t,nd);
	}
}



int main(){ FIN;
	cin>>n;
	ll u,v;
	forn(i,0,n-1){
		cin>>u>>v; u--; v--;
		adj[u].pb(v);
		adj[v].pb(u);
	}	

	string s; cin>>s;
	forn(i,0,n) is[i]=(s[i]=='1');

	ll res = 1;
	mset(down,-1);
	res=max(res,f(0,0,-1));
	forn(i,0,n) res=max(res,f(i,1,pa[i]));
	newf(0,1,-1);

	forn(i,0,n){
		res=max(res,dp[i][1]);
	}

	cout<<res<<'\n';
	
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...