题目描述
给定一棵n个节点的无根树，其中边权只有1或2两种。
现在定义u →v两点之间的距离w (u,v)为两点间简单路径上所有边权的最大公约数。令f(t)表示为节点t到树上其他节点的距离之和。
求min(f(1),f(2),. . . ,f(n))。
现在定义u →v两点之间的距离w (u,v)为两点间简单路径上所有边权的最大公约数。令f(t)表示为节点t到树上其他节点的距离之和。
求min(f(1),f(2),. . . ,f(n))。
输入
第一行包含一个正整数n(1 ≤n≤1e5)，代表这棵树的节点数量。
接下来n-1行，每行三个正整数 u, v, w (1≤u,v≤n,1≤w≤2)，代表u和v之间有一条权值为w的无向边。
接下来n-1行，每行三个正整数 u, v, w (1≤u,v≤n,1≤w≤2)，代表u和v之间有一条权值为w的无向边。
输出
输出一行一个正整数，代表min(f(1),f(2),f(3)...f(n))。
样例输入 Copy
5
1 2 2
2 3 2
1 4 1
4 5 2
样例输出 Copy
5
提示
以节点4 作根时，f(4)= w(4,1)+w(4,2)+w(4,3)+ w(4,5)= ged(1,2)+ gcd(1,2,2)+1十2=1＋1＋1＋2=5
可以证明，没有比上述情况更小的价值。
可以证明，没有比上述情况更小的价值。