题目概述

有一棵既有点权又有边权的树，求 $max\{dist(u,v)\cdot min(u,v)\cdot gcd(u,v)\}$ ，其中 $dist(u,v)$ 表示距离，$min(u,v)$ 表示路径上点权最小值，$gcd(u,v)$ 表示路径上点权 $gcd$ 。

解题报告

套路三合一，学习下姿势。这个东西完全没法求，肯定要想办法（比如爆枚）把其中的若干个去掉，这样就可做了。

我们可以爆枚 $gcd$ ，然后把点权是 $gcd$ 倍数的点和这些点之间的边留下来，再将边按照点权排序之后爆枚，这样就成功去掉了 $min$ 和 $gcd$ ，只需要考虑 $dist$ 最大值。

树？$dist$ 最大值？直径喽。两棵树合并之后直径的端点只会是这两棵树直径的端点，所以可以方便合并。

等下……这样复杂度不是炸飞了吗……其实有用的 $gcd$ 只有有直接边相连的点之间的公共因子，这样所有端点均为 $gcd$ 的倍数的边的和就只有 $O(n\sqrt{max\{A_n\}})$（根本达不到，因为因子个数比 $\sqrt{max\{A_n\}}$ 少很多）。

如果计算 $dist$ 的时候不想有 $log_2n$ 可以用欧拉序，欧拉序就是每个点在访问到的时候加入一次，然后每次儿子做完之后再加入一次。这样可以认为每个点在访问的时候添加了一次，回溯到的时候又添加了一次，所以两个点访问到的位置之间深度最小的就是他们的 $lca$ 。

示例程序

#include<cmath>
#include<cstdio>
#include<cctype>
#include<cstring>
#include<algorithm>
#include<vector>
#define fr first
#define sc second
#define mp make_pair
using namespace std;
typedef long long LL;
const int maxn=100000,maxa=10000,Log=18;

int te,n,a[maxn+5],dep[maxn+5],ID[maxn+5],RMQ[(maxn<<1)+5][Log+5],Lg[(maxn<<1)+5];LL dis[maxn+5],ans;
int E,lnk[maxn+5],son[(maxn<<1)+5],nxt[(maxn<<1)+5],w[(maxn<<1)+5];
vector< pair<int,int> > e[maxa+5];int fat[maxn+5],A[maxn+5],B[maxn+5];

#define Eoln(ch) ((x)==10||(x)==13||(x)==EOF)
inline char readc(){
    static char buf[100000],*l=buf,*r=buf;
    return (l==r&&(r=(l=buf)+fread(buf,1,100000,stdin),l==r))?EOF:*l++;
}
template<typename T> inline int readi(T &x){
    T tot=0;char ch=readc(),lst='+';
    while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();}
    while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc();
    return lst=='-'?x=-tot:x=tot,Eoln(ch);
}
#define Add(x,y,z) (son[++E]=(y),w[E]=(z),nxt[E]=lnk[x],lnk[x]=E)
void Dfs(int x,int pre=0){
    for (int j=(dep[x]=dep[pre]+1,RMQ[ID[x]=++ID[0]][0]=x,lnk[x]);j;j=nxt[j])
        if (son[j]!=pre) dis[son[j]]=dis[x]+w[j],Dfs(son[j],x),RMQ[++ID[0]][0]=x;
}
#define Miner(x,y) (dep[x]<dep[y]?(x):(y))
inline void Make(){
    for (int j=1;(1<<j)<=ID[0];j++)
        for (int i=1;i+(1<<j)-1<=ID[0];i++)
            RMQ[i][j]=Miner(RMQ[i][j-1],RMQ[i+(1<<j-1)][j-1]);
    for (int i=2;i<=ID[0];i++) Lg[i]=Lg[i>>1]+1;
}
inline int LCA(int L,int R){
    L=ID[L];R=ID[R];if (L>R) swap(L,R);int k=Lg[R-L+1];
    return Miner(RMQ[L][k],RMQ[R-(1<<k)+1][k]);
}
#define Dis(x,y) (dis[x]+dis[y]-(dis[LCA((x),(y))]<<1))
inline bool cmp(const pair<int,int> &A,const pair<int,int> &B) {return a[A.fr]>a[B.fr];}
int getfa(int x) {return x==fat[x]?x:fat[x]=getfa(fat[x]);}
inline void Merge(int x,int y){
    if (x==y) return;int X,Y;LL MAX=0,now;
    if ((now=Dis(A[x],A[y]))>MAX) MAX=now,X=A[x],Y=A[y];
    if ((now=Dis(A[x],B[x]))>MAX) MAX=now,X=A[x],Y=B[x];
    if ((now=Dis(A[x],B[y]))>MAX) MAX=now,X=A[x],Y=B[y];
    if ((now=Dis(A[y],B[y]))>MAX) MAX=now,X=A[y],Y=B[y];
    if ((now=Dis(B[x],A[y]))>MAX) MAX=now,X=B[x],Y=A[y];
    if ((now=Dis(B[x],B[y]))>MAX) MAX=now,X=B[x],Y=B[y];
    A[x]=X;B[x]=Y;fat[y]=x;
}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    for (readi(te);te;te--){
        readi(n);for (int i=1;i<=n;i++) readi(a[i]);E=0;memset(lnk,0,sizeof(lnk));
        for (int i=1;i<=maxa;i++) e[i].clear();
        for (int i=1,x,y,z;i<n;i++){
            readi(x);readi(y);readi(z);Add(x,y,z);Add(y,x,z);if (a[x]>a[y]) swap(x,y);
            for (int d=1,S=sqrt(a[x]);d<=S;d++)
                if (!(a[x]%d)){
                    if (!(a[y]%d)) e[d].push_back(mp(x,y));
                    if (d<a[x]/d&&!(a[y]%(a[x]/d))) e[a[x]/d].push_back(mp(x,y));
                }
        }ID[0]=0;Dfs(1);Make();ans=0;
        for (int d=1;d<=maxa;d++){
            sort(e[d].begin(),e[d].end(),cmp);LL MAX=0;
            for (int i=0,si=e[d].size();i<si;i++){
                int x=e[d][i].fr,y=e[d][i].sc;
                fat[x]=A[x]=B[x]=x;fat[y]=A[y]=B[y]=y;
            }
            for (int i=0,si=e[d].size();i<si;i++){
                int x=e[d][i].fr,y=e[d][i].sc;x=getfa(x);y=getfa(y);Merge(x,y);
                MAX=max(MAX,Dis(A[x],B[x]));ans=max(ans,MAX*a[e[d][i].fr]*d);
            }
        }printf("%lld\n",ans);
    }
    return 0;
}