题解：P6287 [COCI 2016/2017 #1] Mag

· · 题解

注意到我完全不会 dp，所以 dp 什么的就滚一边去吧。

先特判答案路径长度为 1 的情况。

以下结论都是基于答案路径长度不为 1 时的讨论。

注意到 1 不会让答案变劣，于是贪心的尽可能多选 1。

我们知道树的直径有这样的性质：

到任意点距离最远的点必是树的一条直径的端点。

于是我们把树分成一个个全为 1 的子树，然后在上面求出一条直径，以直径的两个端点开始各跑一遍 dfs 就可以得到每一个点为端点可以得到的最长全 1 路径。

然后考虑往现在的路径上面加点使其变得更优。

注意到：往答案路径上加的点如果给分子的贡献超过 1，那么一定不优。

证明：

假设原本一条较为优秀的路径长度为 n，我们增加上一个点的代价为 x，加上以后可以连接到的另一条路径长度为 m。

在这里，我们钦定 m\le n，容易发现不影响结论。

假设增加后是优秀的，那么有不等式：

\frac{1+x}{n+m+1}<\frac{1}{n}

移项：

xn<m+1

满足这个不等式的唯一解显然是 x=1 且 m=n。

于是原命题自然就得证了。所以路径上至多出现一个 2，并且不可能出现超过 2 的数字。

同时根据这个还可以发现，2 一定是路径的中点。

枚举树上的每一个 2，利用先前统计好的信息计算答案即可。

做完了，时间复杂度容易做到 O(n)。

哦对了注意到，我有个地方写糖了，取最大值图省事直接排了个序，多吃了一只萝卜，欢迎大家爆踩我 /kel

所以下面给出 O(n\log n) 的代码。

#include<bits/stdc++.h>
#define int long long
#define N 1000005
using namespace std;
int a[N],flc,n;
int dis[N],sta;
vector<int>ve[N];
int vis[N],zj[N];
int ans1,ans2;
void dfs1(int x){
    vis[x]=flc;
    if(dis[sta]<dis[x])sta=x;
    for(int i=0;i<ve[x].size();i++)
    if(vis[ve[x][i]]!=flc&&a[ve[x][i]]==1){
        dis[ve[x][i]]=dis[x]+1;
        dfs1(ve[x][i]);
    }
}
void dfs2(int x,int fa,int dep){
    zj[x]=max(zj[x],dep);
    ans1=max(ans1,zj[x]);
    for(int i=0;i<ve[x].size();i++)
    if(fa!=ve[x][i]&&a[ve[x][i]]==1)dfs2(ve[x][i],x,dep+1);
}
void qwq(int x){
    flc++,dis[x]=0,sta=x,dfs1(x);
    int l=sta;
    x=sta,flc++,dis[x]=0,dfs1(x);
    int r=sta;
    dfs2(l,0,1),dfs2(r,0,1);
}
bool cmp(){
    return ans2<2*ans1;
}
void solve(){
    cin>>n;
    for(int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        ve[u].push_back(v);
        ve[v].push_back(u);
    }
    int mini=1e10;
    for(int i=1;i<=n;i++)
    cin>>a[i],mini=min(mini,a[i]);
    if(mini>1){
        cout<<mini<<"/1";
        return;
    }
    for(int i=1;i<=n;i++)
    if(!vis[i]&&a[i]==1)qwq(i);
    for(int i=1;i<=n;i++)
    if(a[i]==2){
        vector<int>kel;
        for(int j=0;j<ve[i].size();j++)
        if(a[ve[i][j]]==1)kel.push_back(zj[ve[i][j]]);
        sort(kel.begin(),kel.end());
        if(kel.size()<2)continue;
        ans2=max(ans2,min(kel[0],kel[1])*2+1);
    }
    if(cmp())cout<<"1/"<<ans1;
    else cout<<"2/"<<ans2;
}
signed main(){
    int t=1;
    while(t--)solve();
    return 0;
}
// 「不会，我并没有做什么需要让你道谢的事。」

// Nephren Ruq Insania