Submission #1328539

#TimeUsernameProblemLanguageResultExecution timeMemory
1328539blackscreen1Power Plant (JOI20_power)C++20
100 / 100
68 ms21608 KiB
#include <bits//stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<long long, null_type, less<long long>, rb_tree_tag,
             tree_order_statistics_node_update>
    ordered_set;
typedef tree<long long, null_type, less_equal<long long>, rb_tree_tag,
             tree_order_statistics_node_update>
    ordered_multiset;
#define ll long long
#define iloop(m, h) for (auto i = m; i != h; i += (m < h ? 1 : -1))
#define jloop(m, h) for (auto j = m; j != h; j += (m < h ? 1 : -1))
#define kloop(m, h) for (auto k = m; k != h; k += (m < h ? 1 : -1))
#define pll pair<ll, ll>
#define INF 1000000000000000
#define MOD1 1000000007
#define MOD2 998244353
#define MOD3 1000000009
ll n, t1, t2;
vector<ll> adj[200005];
bool act[200005];
ll memo[200005], cans = 0;
string s;
void dp(ll nd, ll pr) {
	for (auto it : adj[nd]) if (it != pr) dp(it, nd);
	memo[nd] = 0;
	ll cma = 0;
	for (auto it : adj[nd]) if (it != pr) memo[nd] += memo[it], cma = max(cma, memo[it]);
	if (act[nd]) {
		if (memo[nd] >= 2) memo[nd]--;
		else if (!memo[nd]) memo[nd]++;
		cans = max(cans, cma + 1);
	}
	//cout << nd << ":" << memo[nd] << "\n";
	cans = max(cans, memo[nd]);
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	memset(memo, -1, sizeof(memo));
	cin >> n;
	iloop(1, n) {
		cin >> t1 >> t2;
		t1--, t2--;
		adj[t1].push_back(t2);
		adj[t2].push_back(t1);
	}
	cin >> s;
	iloop(0, n) act[i] = s[i] - '0';
	dp(0, -1);
	cout << cans;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...