「题解」P6287 [COCI2016-2017#1] Mag

Wenoide · 2020-04-05 23:47:33 · 题解

结论

为方便表述，称一条路径的节点数为其长度。

此题有这样的结论：

• 若不存在魔力值为 1 的节点，则魔力值最小的路径即为魔力值最小的节点。

• 若存在魔力值为 1 的节点，记所有节点的魔力值均为 1 的最长路径的长度为 l，则魔力值最小的路径为下面两者之一：

  1. 一条长度为 l 的路径，所有节点的魔力值均为 1。
  2. 一条长度为 2\times l+1 的路径，第 l+1 个节点的魔力值为 2，其余节点的魔力值均为 1。

证明

下文中的所有内容均在正整数范围内讨论。

记路径 p 的长度为 l(p)，魔力值为 f(p)，所有节点魔力值的乘积为 m(p)。

• 若不存在魔力值为 1 的节点。

  假设路径 p_1 将与路径 p_2 连接为一条新的路径。

  不妨令 f(p_1)<f(p_2)。即 \frac{m(p_1)}{l(p_1)}<\frac{m(p_2)}{l(p_2)}。变形可得 \frac{l(p_2)}{l(p_1)}<\frac{m(p_2)}{m(p_1)}。

  若连接后得到的路径为更优解，则 \frac{m(p_1)\times m(p_2)}{l(p_1)+l(p_2)}<\frac{m(p_1)}{l(p_1)}。

  变形得 m(p_2)-1<\frac{l(p_2)}{l(p_1)}。

  所以 m(p_2)-1<\frac{m(p_2)}{m(p_1)}。

  变形得 (m(p_1)-1)(m(p_1)-1)<1。

  由于不存在魔力值为 1 的节点，m(p_1)-1\ge 1 \bigwedge m(p_2)-1\ge 1。

  不等式无解。即将两条路径合并后一定无法得到更优解。

  显然，此时魔力值最小的路径即为魔力值最小的节点。即结论的第一部分。

• 若存在魔力值为 1 的节点。

  假设有最长的路径 p_1 使得 m(p_1)=1，与任意路径 p_2。

  若 f(p_2)<f(p_1)，则 \frac{m(p_2)}{l(p_2)}<\frac{1}{l(p_1)}。

  变形得 \frac{l(p_2)}{l(p_1)}>m(p_2)。

  需要注意，假设 p_2 有最长的子路径 p_t 使得 m(p_t)=1，其还应满足 l(p_t)\le l(p_1)。

  设 m(p_2) 的质因数个数为 k。用魔力值为这些质因数的 k 个节点连接 k+1 段长度为 l(p_1)、魔力值为 1 的路径，即可得到 l(p_2)\le k+(k+1)\times l(p_1)。

  由于 x 的质因数个数不大于 \log_2(x)。所以 l(p_2)\le \log_2(m(p_2))+(\log_2(m(p_2))+1)\times l(p_1)。

  又有 l(p1)\ge 1。所以 2\times \log_2(m(p_2))+1>m(p_2)。

  这个不等式的正整数解为 m(p_2)=2,3,4,5,6。

  经检验，只有当 m(p_2)=2,4 时，关于 l(p_1) 的不等式 \frac{k+ (k+1)\times l(p_1)}{l(p_1)}>m(p_2) 有正整数解。

  1. 此时 $l(p_1)=1$。即路径 $p_2$ 为 `1,2,1,2,1`。 但是，这条路径的魔力值大于路径 `1,2,1`。
  2. 不等式恒成立。 即当 $l(p_2)=2\times l(p_1)+1$，路径 $p_2$ 的第 $l(p_1)+1$ 个节点的魔力值为 $2$，其余节点的魔力值均为 $1$ 时，$f(p_2)<f(p_1)$。 若 $l(p_2)$ 不再取最大值 $k+(k+1)\times l(p_1)$，不等式无正整数解。

  换言之，当且仅当 l(p_2)=2\times l(p_1)+1，第 l(p_1)+1 个节点的魔力值为 2，其余节点的魔力值均为 1 时，f(p_2)<f(p_1)。即结论的第二部分。

实现

实际上，我们可以统计所有仅有一个节点的魔力值为 2、其余节点魔力值均为 1 的路径，不影响答案。因为若魔力值为 2 的节点不在该路径正中间，则一定存在一条所有节点魔力值均为 1 的子路径，魔力值不小于原路径。

若子路径的魔力值和原路径相等，便可能出现需要约分的情况。我们可以优化统计答案的顺序，使得子路径的魔力值一定先于原路径被统计。

• 用 f(x) 表示以 x 为根节点的子树中，以 x 为一端且魔力值为 1 的路径的最大长度。

• 用 g(x) 表示以 x 为根节点的子树中，以 x 为一端且魔力值为 2 的路径的最大长度。

• 节点 x 得出的答案由其自身与两个不同的子节点 i,j（可能为空）组成：

  1. 节点 x 的魔力值为 1。

     得出的答案为 1/(\max(f(i)+f(j))+1) 与 2/(\max(f(i)+g(j))+1)。

  2. 节点 x 的魔力值为 2。

     得出的答案为 2/\max(f(i)+f(j))+1。

  3. 节点 x 的魔力值大于 2。

     无法得出答案。

参考代码：

//注：本人实现代码时参考了 @programme_C 的题解。
#include<cstdio>
const int MAXN=1000000+10;
struct Node{
    int next;
    int to;
}edge[MAXN<<1];
int head[MAXN],cnt;
void add(int u,int v){
    edge[cnt].next=head[u];
    edge[cnt].to=v;
    head[u]=cnt++;
    return;
}
int mag[MAXN];
int f[MAXN],g[MAXN];
int p=1e9,q=1,mn=1e9;
void update(int x,int y){
    if(p*y>q*x){
        p=x,q=y;
    }
    return;
}
//更新答案。化除为乘。
void DP(int cur,int fa){
    int u1=0,u2=0,v1=0,v2=0;
    /*
        u1 表示 cur 的子结点中 f 值最大的节点；
        u2 表示 cur 的子结点中 f 值次大的节点；
        v1 表示 cur 的子结点中 g 值最大的节点；
        v2 表示 cur 的子结点中 g 值次大的节点；
    */
    for(int i=head[cur];~i;i=edge[i].next){
        int t=edge[i].to;
        if(t!=fa){
            DP(t,cur);
            if(f[t]>f[u1]){
                u2=u1,u1=t;
            }
            else if(f[t]>f[u2]){
                u2=t;
            }
            if(g[t]>g[v1]){
                v2=v1,v1=t;
            }
            else if(g[t]>g[v2]){
                v2=t;
            }
        }
        //更新 u1,u2,v1,v2。
    }
    if(mag[cur]==1){
        f[cur]=f[u1]+1;
        update(1,f[u1]+f[u2]+1);
        //注意顺序。避免出现需要约分的情况。
        if(v1!=0){
            g[cur]=g[v1]+1;
            if(u1!=v1){
                update(2,f[u1]+g[v1]+1);
            }
            //特判 cur 的子结点中 f 值最大的节点与 g 值最大的节点相同的情况。
            else{
                update(2,f[u2]+g[v1]+1);
                if(v2!=0){
                    update(2,f[u1]+g[v2]+1);
                }
            }
        }
        //特判 g 值为 0 的情况。此时无法构成符合要求的路径。
        //需要注意，f 值为 0 时仍能构成符合要求的路径。
    }
    else if(mag[cur]==2){
        g[cur]=f[u1]+1;
        update(2,f[u1]+f[u2]+1);
    }
    return;
}
int main(){
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        head[i]=-1;
    }
    for(int i=1;i<n;++i){
        int u,v;
        scanf("%d%d",&u,&v);
        add(u,v);
        add(v,u);
    }
    for(int i=1;i<=n;++i){
        scanf("%d",mag+i);
        if(mag[i]<mn){
            mn=mag[i];
        }
    }
    if(mn>1){
        printf("%d/1",mn);
        return 0;
    }
    //特判无魔力值为 1 的节点的情况。
    DP(1,0);
    printf("%d/%d",p,q);
    return 0;
}