#include <bits/stdc++.h>
using namespace std;
template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl
using ll = long long;
const ll mod = 1e9+7;
const int maxn = 1e6 + 5;
int n;
vector<int> g[maxn];
string s;
int best=0;
int dfs(int at, int p) {
vector<int> ch;
for (int to: g[at]) {
if (to==p) continue;
int rec=dfs(to,at);
if (rec>0) {
ch.push_back(rec);
}
}
int res=int(s[at]-'0'); // self
if (!ch.empty()) {
sort(ch.begin(), ch.end());
// self + best child
if (s[at]=='1') {
best=max(best,1+ch.back());
}
// join children thru us
int sum = std::accumulate(ch.begin(), ch.end(), 0);
res = max(res, sum - int(s[at]-'0'));
}
cout<<at+1<<": "<<res<<endl;
cout<<"ch: ";
for (int c: ch) cout<<c<<" ";
cout<<endl;
best=max(best,res);
return res;
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin>>n;
for (int i=0; i<n-1; i++) {
int u,v; cin>>u>>v;
--u; --v;
g[u].push_back(v);
g[v].push_back(u);
}
cin>>s;
dfs(0,-1);
// for (int i=0; i<n; i++) {
// dfs(i,-1);
// }
cout<<best<<endl;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
23808 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
23808 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
23808 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
