#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef stack<ll> sll;
typedef queue<ll> qll;
typedef deque<ll> dll;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;
#define endl '\n'
#define pb push_back
#define FOR(i,a,b) for(int i = a; i <= b; i++)
#define BACK(i,a,b) for(int i = a; i >= b; i--)
#define fastIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define fi first
#define se second
#define bp __builtin_popcountll
#define gcd __gcd
#define bit(i,n) ((n>>i)&1)
#define setmin(x,y) x=min((x),(y))
#define setmax(x,y) x=max((x),(y))
const int MAXN = (2e5)+5;
// const ll SQRT = 4;
const long long inf = 1e18;
const long long MOD = 998244353;
vector<int> adj[MAXN];
int n,f[MAXN],ans,par[MAXN],cnt[MAXN];
bool gen[MAXN];
int dp(int u)
{
if(f[u]!=INT_MAX) return f[u];
int res=cnt[u]-gen[u];
for(auto v:adj[u]) if(v!=par[u]) if(dp(v)-gen[u]-gen[v]>0) res+=dp(v)-gen[u]-gen[v];
return f[u]=res;
}
void dfs(int u)
{
for(auto v:adj[u]) if(v!=par[u])
{
par[v]=u;
dfs(v);
}
}
signed main()
{
fastIO
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
cin>>n;
FOR(i,1,n-1)
{
int u,v;
cin>>u>>v;
adj[u].pb(v);
adj[v].pb(u);
}
FOR(i,1,n)
{
char c;
cin>>c;
gen[i]=(c=='1');
}
dfs(1);
FOR(i,1,n) f[i]=INT_MAX;
FOR(i,1,n) for(auto a:adj[i]) cnt[i]+=gen[a];
FOR(i,1,n) ans=max(ans,dp(i));
cout<<ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
4948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
4948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
4948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
