#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define all(x) x.begin(), x.end()
#define Neco "Power Plant"
#define resp(x) sort(all(x)), x.resize(unique(all(x)) - x.begin())
#define getbit(x,i) ((x >> i)&1)
#define _left id * 2, l, mid
#define _right id * 2 + 1, mid + 1, r
#define cntbit(x) __builtin_popcountll(x)
#define fi(i, a, b) for(int i = a; i <= b; i++)
#define fid(i, a, b) for(int i = a; i >= b; i--)
#define maxn (int) 2e5 + 7
using namespace std;
const ll mod = 1e9 + 7; //972663749
const ll base = 911382323;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll GetRandom(ll l, ll r)
{
return uniform_int_distribution<ll> (l, r)(rng);
}
int n, res = 1;
int dp[maxn], cl[maxn];
vector<int> edges[maxn];
void dfs(int u, int par)
{
vector<int> P;
for(int v : edges[u]) if(v != par) {
dfs(v, u);
P.push_back(dp[v]);
}
sort(all(P), greater<int>());
int ans = cl[u];
int sum = 0;
if(P.size() >= 1)
{
res = max(res, P[0] + cl[u]), ans = max(ans, P[0] + cl[u]);
fi(i, 0, P.size() - 1) {
sum += P[i];
if(i > 1) res = max(res, sum - cl[u]), ans = max(ans, sum - cl[u]);
}
dp[u] = sum;
}
if(cl[u]) dp[u] = max(dp[u] - 1, 1);
// cout << u << " " << dp[u] << " " << ans << '\n';
}
void Input()
{
cin >> n;
fi(i, 1, n - 1) {
int x, y;
cin >> x >> y;
edges[x].push_back(y), edges[y].push_back(x);
}
fi(i, 1, n) {
char x; cin >> x;
cl[i] = x - '0';
}
}
void gen()
{
n = GetRandom(2, 15);
cout << n << '\n';
fi(i, 1, n - 1) {
int x = i + 1, y = GetRandom(1, i);
edges[x].push_back(y), edges[y].push_back(x);
cout << x << " " << y << '\n';
}
fi(i, 1, n) cl[i] = 1;
fi(i, 1, n) cout << cl[i];
cout << '\n';
cout << "-------------------\n";
}
void solve()
{
Input();
// gen();
dfs(1, 0);
cout << res;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
if(fopen(Neco".inp", "r")) {
freopen(Neco".inp", "r", stdin);
freopen(Neco".out", "w", stdout);
}
int nTest = 1;
// cin >> nTest;
while(nTest--)
{
solve();
}
return 0;
}
Compilation message
power.cpp: In function 'void dfs(int, int)':
power.cpp:12:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
12 | #define fi(i, a, b) for(int i = a; i <= b; i++)
......
49 | fi(i, 0, P.size() - 1) {
| ~~~~~~~~~~~~~~~~~~
power.cpp:49:9: note: in expansion of macro 'fi'
49 | fi(i, 0, P.size() - 1) {
| ^~
power.cpp: In function 'int main()':
power.cpp:116:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
116 | freopen(Neco".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
power.cpp:117:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
117 | freopen(Neco".out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
4956 KB |
Output is correct |
| 2 |
Correct |
2 ms |
4956 KB |
Output is correct |
| 3 |
Correct |
2 ms |
4956 KB |
Output is correct |
| 4 |
Incorrect |
2 ms |
5136 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
4956 KB |
Output is correct |
| 2 |
Correct |
2 ms |
4956 KB |
Output is correct |
| 3 |
Correct |
2 ms |
4956 KB |
Output is correct |
| 4 |
Incorrect |
2 ms |
5136 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
4956 KB |
Output is correct |
| 2 |
Correct |
2 ms |
4956 KB |
Output is correct |
| 3 |
Correct |
2 ms |
4956 KB |
Output is correct |
| 4 |
Incorrect |
2 ms |
5136 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
