#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N =1e5+4;
int n;
vector <int> g[N];
int on[N];
ll dp[N][2][2]; /// i-ti cvor, j-da li je upaljen ili ne,k-da li je na njemu izvrsena operacija ili ne
bool cmp1(pair <ll,ll> x,pair <ll,ll> y){
return (x.second-x.first < y.second-y.first);
}
bool cmp2(pair <ll,ll> x,pair <ll,ll> y){
return (x.first-x.second < y.first-y.second);
}
void dfs(int x,int par){
if(g[x].size() == 1 && x != 1){
if(on[x]){
dp[x][1][0] = 0;
dp[x][0][1] = 1;
}
else{
dp[x][0][0] = 0;
dp[x][1][1] = 1;
}
/*cout << "postavio " << x << endl;
cout << dp[x][0][0] << " " << dp[x][0][1] << " " << dp[x][1][0] << " " << dp[x][1][1] << endl;*/
return;
}
for(auto f : g[x]){
if(f == par) continue;
dfs(f,x);
}
/// svi vec ugaseni tj dp[child][0][0/1]
vector <pair<ll,ll>> vdole,vgore,v;
for(auto f : g[x]){
if(f == par) continue;
if(dp[f][0][1] < dp[f][0][0]) vgore.push_back({dp[f][0][1],dp[f][0][0]}); /// nagore
else vdole.push_back({dp[f][0][1],dp[f][0][0]}); /// nadole
}
if(!vgore.empty()) for(auto f : vgore) v.push_back(f);
if(!vdole.empty()) for(auto f : vdole) v.push_back(f);
/*for(auto f : vgore) cout << f.first << " a " << f.second << endl;
cout << endl;
for(auto f : vdole) cout << f.first << " b " << f.second << endl;
cout << endl;*/
/// pokusaj parno ili neparno keceva
ll sumgore = 0,sumdole = 0;
if(!vgore.empty()) for(auto f : vgore) sumgore += f.first;
if(!vdole.empty()) for(auto f : vdole) sumdole += f.second;
vector <pair<ll,ll>> vgoresrt = vgore;
if(!vgoresrt.empty()) sort(vgoresrt.begin(),vgoresrt.end(),cmp1);
vector <ll> vgsvalfr(vgoresrt.size()+1,0),vgsvalsc(vgoresrt.size()+1,0);
if(!vgoresrt.empty()){
vgsvalsc[0] = vgoresrt[0].second;
vgsvalfr[0] = vgoresrt[0].first;
for(int i = 1; i < vgoresrt.size(); i++){
vgsvalfr[i] = vgsvalfr[i-1]+vgoresrt[i].first;
vgsvalsc[i] = vgsvalsc[i-1]+vgoresrt[i].second;
}
}
vector <pair<ll,ll>> vdolesrt = vdole;
if(!vdolesrt.empty()) sort(vdolesrt.begin(),vdolesrt.end(),cmp2);
vector <ll> vdsvalfr(vdolesrt.size()+1,0),vdsvalsc(vdolesrt.size()+1,0);
if(!vdolesrt.empty()){
vdsvalfr[0] = vdolesrt[0].first;
vdsvalsc[0] = vdolesrt[0].second;
for(int i = 1; i < vdolesrt.size(); i++){
vdsvalfr[i] = vdsvalfr[i-1]+vdolesrt[i].first;
vdsvalsc[i] = vdsvalsc[i-1]+vdolesrt[i].second;
}
}
ll minvalpar = 7e18,minvalnep = 7e18;
for(int i = 0; i < v.size(); i++){
ll val = 0;
if(i < vgore.size()){
val = sumgore+sumdole;
if(i != vgore.size()-1) val += -vgsvalfr[vgore.size()-i-2]+vgsvalsc[vgore.size()-i-2];
}
else{
val = sumgore+sumdole;
val += -vdsvalsc[i-vgore.size()]+vdsvalfr[i-vgore.size()];
}
if(i&1) minvalpar = min(minvalpar,val);
else minvalnep = min(minvalnep,val);
}
if(on[x]) dp[x][1][0] = min(dp[x][1][0],minvalpar);
else dp[x][0][0] = min(dp[x][0][0],minvalpar);
if(on[x]) dp[x][0][0] = min(dp[x][0][0],minvalnep);
else dp[x][1][0] = min(dp[x][1][0],minvalnep);
/// svi upaljeni tj dp[child][1][0/1]
vdole.clear();
vgore.clear();
v.clear();
vgsvalfr.clear();
vgsvalsc.clear();
vdsvalfr.clear();
vdsvalsc.clear();
for(auto f : g[x]){
if(f == par) continue;
if(dp[f][1][1] < dp[f][1][0]) vgore.push_back({dp[f][1][1],dp[f][1][0]}); /// nagore
else vdole.push_back({dp[f][1][1],dp[f][1][0]}); /// nadole
}
if(!vgore.empty()) for(auto f : vgore) v.push_back(f);
if(!vdole.empty()) for(auto f : vdole) v.push_back(f);
/*for(auto f : vgore) cout << f.first << " c " << f.second << endl;
cout << endl;
for(auto f : vdole) cout << f.first << " d " << f.second << endl;
cout << endl;*/
/// pokusaj parno ili neparno keceva
sumgore = 0,sumdole = 0;
if(!vgore.empty()) for(auto f : vgore) sumgore += f.first;
if(!vdole.empty()) for(auto f : vdole) sumdole += f.second;
vgoresrt = vgore;
if(!vgoresrt.empty()) sort(vgoresrt.begin(),vgoresrt.end(),cmp1);
vgsvalfr.resize(vgoresrt.size()+1,0);
vgsvalsc.resize(vgoresrt.size()+1,0);
if(!vgoresrt.empty()){
vgsvalsc[0] = vgoresrt[0].second;
vgsvalfr[0] = vgoresrt[0].first;
for(int i = 1; i < vgoresrt.size(); i++){
vgsvalfr[i] = vgsvalfr[i-1]+vgoresrt[i].first;
vgsvalsc[i] = vgsvalsc[i-1]+vgoresrt[i].second;
}
}
vdolesrt = vdole;
if(!vdolesrt.empty()) sort(vdolesrt.begin(),vdolesrt.end(),cmp2);
vdsvalfr.resize(vdolesrt.size()+1,0);
vdsvalsc.resize(vdolesrt.size()+1,0);
if(!vdolesrt.empty()){
vdsvalfr[0] = vdolesrt[0].first;
vdsvalsc[0] = vdolesrt[0].second;
for(int i = 1; i < vdolesrt.size(); i++){
vdsvalfr[i] = vdsvalfr[i-1]+vdolesrt[i].first;
vdsvalsc[i] = vdsvalsc[i-1]+vdolesrt[i].second;
}
}
minvalpar = 7e18,minvalnep = 7e18;
for(int i = 0; i < v.size(); i++){
ll val = 0;
if(i < vgore.size()){
val = sumgore+sumdole;
if(i != vgore.size()-1) val += -vgsvalfr[vgore.size()-i-2]+vgsvalsc[vgore.size()-i-2];
}
else{
val = sumgore+sumdole;
val += -vdsvalsc[i-vgore.size()]+vdsvalfr[i-vgore.size()];
}
if(i&1) minvalpar = min(minvalpar,val);
else minvalnep = min(minvalnep,val);
}
if(on[x]) dp[x][0][1] = min(dp[x][0][1],minvalpar);
else dp[x][1][1] = min(dp[x][1][1],minvalpar);
if(on[x]) dp[x][1][1] = min(dp[x][1][1],minvalnep);
else dp[x][0][1] = min(dp[x][0][1],minvalnep);
//cout << "kraj " << x << " " << dp[x][0][0] << " " << dp[x][0][1] << " " << dp[x][1][0] << " " << dp[x][1][1] << endl;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> n;
for(int i = 1; i < n; i++){
int u,v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
for(int i = 1; i <= n; i++){
cin >> on[i];
}
for(int i = 1; i <= n; i++){
dp[i][0][0] = dp[i][0][1] = dp[i][1][0] = dp[i][1][1] = 1e9;
}
dfs(1,0);
ll sol = min(dp[1][0][0],dp[1][0][1]);
if(sol >= 1e9) cout << "impossible" << endl;
else if(dp[1][0][0] < dp[1][0][1]) cout << dp[1][0][0] << endl;
else cout << dp[1][0][1]+1 << endl;
}
Compilation message
xanadu.cpp: In function 'void dfs(int, int)':
xanadu.cpp:65:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
65 | for(int i = 1; i < vgoresrt.size(); i++){
| ~~^~~~~~~~~~~~~~~~~
xanadu.cpp:77:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
77 | for(int i = 1; i < vdolesrt.size(); i++){
| ~~^~~~~~~~~~~~~~~~~
xanadu.cpp:84:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
84 | for(int i = 0; i < v.size(); i++){
| ~~^~~~~~~~~~
xanadu.cpp:86:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
86 | if(i < vgore.size()){
| ~~^~~~~~~~~~~~~~
xanadu.cpp:88:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
88 | if(i != vgore.size()-1) val += -vgsvalfr[vgore.size()-i-2]+vgsvalsc[vgore.size()-i-2];
| ~~^~~~~~~~~~~~~~~~~
xanadu.cpp:139:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
139 | for(int i = 1; i < vgoresrt.size(); i++){
| ~~^~~~~~~~~~~~~~~~~
xanadu.cpp:152:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
152 | for(int i = 1; i < vdolesrt.size(); i++){
| ~~^~~~~~~~~~~~~~~~~
xanadu.cpp:159:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
159 | for(int i = 0; i < v.size(); i++){
| ~~^~~~~~~~~~
xanadu.cpp:161:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
161 | if(i < vgore.size()){
| ~~^~~~~~~~~~~~~~
xanadu.cpp:163:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
163 | if(i != vgore.size()-1) val += -vgsvalfr[vgore.size()-i-2]+vgsvalsc[vgore.size()-i-2];
| ~~^~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
2644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
2644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
99 ms |
57292 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
104 ms |
57340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
2644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
