#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);
int n;
vi v[1000009];
int a[1000009];
int dpdn[1000009];
void dfs1(int node,int 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);
}
}
int dpup[1000009];
void dfs2(int node,int p){
vi pre,suf;
pre.pb(0),suf.pb(0);
for(auto u:v[node]){
if(u==p)C;
int 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;
int 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++;
int mx=0;
int bef=pre[it-1];
int aft=suf[it];
if(a[node]==1)mx=max(dpup[node],max(bef,aft))+1;
dpup[u]=mx;
dfs2(u,node);
}
}
pi ans={1e9,1};
bool yes(pi a,pi b){
return (ll)a.fi*b.se<(ll)b.fi*a.se;
}
void calc(int node,int p){
pi ret={a[node],1};
if(yes(ret,ans))ans=ret;
int mx=dpup[node];
for(auto u:v[node]){
if(u==p)C;
int 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);
if(G==0){
while(1){
}
}
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 |
23800 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
20 ms |
23928 KB |
Output is correct |
| 2 |
Correct |
22 ms |
24056 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1418 ms |
146144 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
19 ms |
23800 KB |
Output is correct |
| 2 |
Runtime error |
1586 ms |
262144 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
1620 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1430 ms |
67080 KB |
Output is correct |
| 2 |
Correct |
1039 ms |
55904 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1515 ms |
70460 KB |
Output is correct |
| 2 |
Correct |
203 ms |
28284 KB |
Output is correct |
| 3 |
Runtime error |
1669 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
202 ms |
28280 KB |
Output is correct |
| 2 |
Correct |
1451 ms |
68676 KB |
Output is correct |
| 3 |
Correct |
955 ms |
45944 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1379 ms |
67356 KB |
Output is correct |
| 2 |
Correct |
1510 ms |
66228 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1511 ms |
68232 KB |
Output is correct |
| 2 |
Correct |
952 ms |
46140 KB |
Output is correct |
