#include <bits/stdc++.h>
using namespace std;
bool ch[200009];
int ch2[200009], cnt = 0;
vector<int> graph[200009];
int a[200009], sz[200009], dp[200009], ans = 0;
char s[200009];
void getsize(int v){
ch2[v] = cnt;
sz[v] = 1;
for(int i=0; i<graph[v].size(); i++){
int u = graph[v][i];
if(!ch[u] && ch2[u] != cnt){
getsize(u);
sz[v] += sz[u];
}
}
}
int centroid(int v, int crit){
ch2[v] = cnt;
//printf("v=%d sz=%d crit=%d\n", v, sz[v], crit);
for(int i=0; i<graph[v].size(); i++){
int u = graph[v][i];
if(!ch[u] && ch2[u] != cnt){
if(sz[u] > crit)
return centroid(u, crit);
}
}
return v;
}
void treedp(int v){
ch2[v] = cnt;
int sum = 0, mx = 0;
for(int i=0; i<graph[v].size(); i++){
int u = graph[v][i];
if(!ch[u] && ch2[u] != cnt){
treedp(u);
sum += dp[u];
mx = max(mx, dp[u]);
}
}
dp[v] = max(max(a[v], mx), sum - a[v]);
}
void solve(int v){
cnt++;
getsize(v);
cnt++;
int c=centroid(v, sz[v]/2), i, u, temp = 1;
ch[c]=1;
for(i=0; i<graph[v].size(); i++){
u = graph[v][i];
if(!ch[u]){
if(a[u])
temp = 2;
}
}
cnt++;
treedp(c);
temp = max(dp[c], temp);
//printf("c=%d dp[c]=%d\n", c, dp[c]);
ans = max(ans, temp);
for(i=0; i<graph[v].size(); i++){
u = graph[v][i];
if(!ch[u]){
solve(u);
}
}
}
int main(){
int n, u, b, i;
scanf("%d", &n);
for(i=1; i<n; i++){
scanf("%d %d", &u, &b);
graph[u].push_back(b);
graph[b].push_back(u);
}
scanf(" %s", s+1);
for(i=1; i<=n; i++)
a[i] = s[i] - '0';
solve(1);
printf("%d\n", ans);
return 0;
}
Compilation message
power.cpp: In function 'void getsize(int)':
power.cpp:11:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
11 | for(int i=0; i<graph[v].size(); i++){
| ~^~~~~~~~~~~~~~~~
power.cpp: In function 'int centroid(int, int)':
power.cpp:22:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
22 | for(int i=0; i<graph[v].size(); i++){
| ~^~~~~~~~~~~~~~~~
power.cpp: In function 'void treedp(int)':
power.cpp:34:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
34 | for(int i=0; i<graph[v].size(); i++){
| ~^~~~~~~~~~~~~~~~
power.cpp: In function 'void solve(int)':
power.cpp:50:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
50 | for(i=0; i<graph[v].size(); i++){
| ~^~~~~~~~~~~~~~~~
power.cpp:62:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
62 | for(i=0; i<graph[v].size(); i++){
| ~^~~~~~~~~~~~~~~~
power.cpp: In function 'int main()':
power.cpp:71:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
71 | scanf("%d", &n);
| ~~~~~^~~~~~~~~~
power.cpp:73:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
73 | scanf("%d %d", &u, &b);
| ~~~~~^~~~~~~~~~~~~~~~~
power.cpp:77:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
77 | scanf(" %s", s+1);
| ~~~~~^~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3 ms |
4956 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
4956 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3 ms |
4956 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
4956 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3 ms |
4956 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
4956 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
