| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 365376 | FatihSolak | Mag (COCI16_mag) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define N 1000005
using namespace std;
vector<int> adj[N];
int arr[N];
int down[N];
int d[N];
int up[N];
int maxi = 0,mini = 1e9;
void dfs(int v,int p){
for(auto u:adj[v]){
if(u == p)continue;
dfs(u,v);
if(arr[u] == 1){
down[v] = max(down[v],down[u] + 1);
if(down[v] == down[u] + 1)d[v] = u;
}
}
for(auto u:adj[v]){
if(u == p)continue;
if(d[v] != u){
down2[v] = max(down2[v],down[u]+1);
}
}
}
void dfs2(int v,int p){
if(arr[p] == 1){
up[v] = up[p] + 1;
if(arr[v] == 1 && d[p] == v){
up[v] = max(up[v], down2[p]+1);
}
else up[v] = max(up[v], down[p]+1);
}
for(auto u:adj[v]){
if(u == p)continue;
dfs2(u,v);
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
int n;
cin >> n;
for(int i=1;i<n;i++){
int u,v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
for(int i=1;i<=n;i++){
cin >> arr[i];
}
dfs(1,0);
dfs2(1,0);
for(int i=1;i<=n;i++){
if(arr[i] == 1){
maxi = max(maxi,2*(1+down[i]+up[i]));
}
if(arr[i] == 2){
maxi = max(maxi,1+down[i]+up[i]);
}
mini = min(mini,arr[i]);
}
if(maxi == 0){
cout << mini << "/" <<1;
}
else if(maxi & 1){
cout << 2 << "/" << maxi;
}
else cout << 1 << "/" << maxi/2;
}