自动搬运

查看原文

来自洛谷，原作者为

	Wenoide Wrong answer on line 1 column 12.

搬运于2025-08-24 22:19:21，当前版本为作者最后更新于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. $m(p_2)=4$。

     此时 $l(p_1)=1$。即路径 $p_2$ 为 1,2,1,2,1。

     但是，这条路径的魔力值大于路径 1,2,1。

  2. $m(p_2)=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)$。

     $f(x)=\max(f(i))+1,g(x)=\max(g(i))+1$。

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

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

     $f(x)=0,g(x)=\max(f(i))+1$。

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

     无法得出答案。

     $f(x)=0,g(x)=0$。

参考代码：

//注：本人实现代码时参考了 @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;
}