#define fast ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#include <bits/stdc++.h>
using namespace std;
#define sqr 340
#define mid (l+r)/2
#define pb push_back
#define ppb pop_back
#define fi first
#define se second
#define lb lower_bound
#define ub upper_bound
#define ins insert
#define era erase
#define C continue
#define mem(dp,i) memset(dp,i,sizeof(dp))
#define mset multiset
typedef long long ll;
typedef short int si;
typedef long double ld;
typedef pair<int,int> pi;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pi> vpi;
typedef vector<pll> vpll;
const ll mod=1e9+7;
const ll inf=1e18;
const ld pai=acos(-1);
ll n;
vll v[1000009];
ll a[1000009];
ll dpdn[1000009];
void dfs1(ll node,ll p){
for(auto u:v[node]){
if(u==p)C;
dfs1(u,node);
if(a[u]!=1)C;
dpdn[node]=max(dpdn[node],dpdn[u]+1);
}
}
ll dpup[1000009];
void dfs2(ll node,ll p){
vll pre,suf;
pre.pb(0),suf.pb(0);
for(auto u:v[node]){
if(u==p)C;
ll val=0;
if(a[u]==1)val=dpdn[u]+1;
pre.pb(max(pre[pre.size()-1],val));
}
for(int i=v[node].size()-1;i>=0;i--){
int u=v[node][i];
if(u==p)C;
ll val=0;
if(a[u]==1)val=dpdn[u]+1;
suf.pb(max(suf[suf.size()-1],val));
}reverse(suf.begin(),suf.end());
int it=0;
for(auto u:v[node]){
if(u==p)C;
it++;
ll mx=0;
ll bef=pre[it-1];
ll aft=suf[it];
if(a[node]==1)mx=max(dpup[node],max(bef,aft))+1;
dpup[u]=mx;
dfs2(u,node);
}
}
pll ans={1e9,1};
bool yes(pll a,pll b){
return (ll)a.fi*b.se<(ll)b.fi*a.se;
}
void calc(int node,int p){
pll ret={a[node],1};
if(yes(ret,ans))ans=ret;
ll mx=dpup[node];
for(auto u:v[node]){
if(u==p)C;
ll val=0;
if(a[u]==1)val=dpdn[u]+1;
ret={a[node],1+val+mx};
if(yes(ret,ans))ans=ret;
mx=max(mx,val);
calc(u,node);
}
}
int main(){
cin>>n;
for(int i=0;i<n-1;i++){
int a,b;
cin>>a>>b;
a--,b--;
v[a].pb(b);
v[b].pb(a);
}
for(int i=0;i<n;i++)cin>>a[i];
dfs1(0,0);
dfs2(0,0);
calc(0,0);
ll G=__gcd(ans.fi,ans.se);
cout<<(ll)ans.fi/G<<"/"<<(ll)ans.se/G<<endl;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
21 ms |
23928 KB |
Output is correct |
| 2 |
Correct |
19 ms |
23928 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
21 ms |
23928 KB |
Output is correct |
| 2 |
Correct |
20 ms |
23932 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1391 ms |
169344 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
19 ms |
23800 KB |
Output is correct |
| 2 |
Runtime error |
1615 ms |
262144 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
1623 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1451 ms |
93780 KB |
Output is correct |
| 2 |
Correct |
1079 ms |
75960 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1558 ms |
103404 KB |
Output is correct |
| 2 |
Correct |
220 ms |
31608 KB |
Output is correct |
| 3 |
Runtime error |
1647 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
224 ms |
31352 KB |
Output is correct |
| 2 |
Correct |
1470 ms |
95480 KB |
Output is correct |
| 3 |
Correct |
990 ms |
61944 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1397 ms |
94948 KB |
Output is correct |
| 2 |
Correct |
1542 ms |
95304 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1460 ms |
95764 KB |
Output is correct |
| 2 |
Correct |
990 ms |
61908 KB |
Output is correct |
