【题目】
CC
给定一棵n个点带点权和边权的树,求树上所有路径中dis(u,v)⋅gcd(u,v)⋅min(u,v)的最大值,括号内点对均表示两点间路径。
n≤105,边权≤105,点权≤104,100组数据。
【解题思路】
没有什么好的想法,写个暴力。
对于所有可能的gcd来说,每条边最多在其中约数个数个中出现,那么总的出现次数(松的)上界就是O(n34)了。
枚举这个gcd,然后从大到小将每条可行的边加入图中,那么当前加入的边一定是min。再维护一下连通块的直径就可以直接算了。
虽然算的结果对于当前不一定是正确的,但我们最终一定能得到最优的值。
lca写O(1)的,那么一个十分松的上界大概就是O(n34)了(因为点权是104的不到n级别,不过我预处理是根号的),但它常数比较大,而且我写得比较懒,还有100组数据。。。所以随便了。
其实我写完是很懵的,怎么写着写着就过了???我都开始打对拍了???
#include<bits/stdc++.h>
#define pb push_back
using namespace std;
typedef long long ll;
const int N=1e5+10,M=1e4+10;
namespace IO
{
int read()
{
int ret=0;char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) ret=ret*10+(c^48),c=getchar();
return ret;
}
void write(int x){if(x>9)write(x/10);putchar(x%10^48);}
void writeln(int x){write(x);putchar('\n');}
}
using namespace IO;
namespace Tree
{
int tot,ind;
int f[N],fc[25],Log[N<<1];
int head[N],fa[N],pos[N],dfn[N<<1],st[19][N<<1];
ll dis[N];
struct edge{int u,v,w;edge(int _u=0,int _v=0,int _w=0):u(_u),v(_v),w(_w){}}E[N];
struct Tway{int v,w,nex;}e[N<<1];
struct data{int x,y;data(int _x=0,int _y=0):x(_x),y(_y){}}d[N];
void add(int u,int v,int w)
{
e[++tot]=(Tway){v,w,head[u]};head[u]=tot;
e[++tot]=(Tway){u,w,head[v]};head[v]=tot;
}
void dfs(int x)
{
dfn[++ind]=x;pos[x]=ind;
for(int i=head[x];i;i=e[i].nex)
{
int v=e[i].v;
if(v==fa[x]) continue;
fa[v]=x;dis[v]=dis[x]+e[i].w;
dfs(v);dfn[++ind]=x;
}
}
int cmp(int x,int y){return dis[x]<dis[y]?x:y;}
void initst()
{
for(int i=1;i<=ind;++i) st[0][i]=dfn[i];
for(int j=1;j<20;++j) for(int i=1;i+fc[j]-1<=ind;++i)
st[j][i]=cmp(st[j-1][i],st[j-1][i+fc[j-1]]);
}
int lca(int x,int y)
{
int l=pos[x],r=pos[y];
if(l>r) swap(l,r);
int k=Log[r-l+1];
return cmp(st[k][l],st[k][r-fc[k]+1]);
}
ll getdis(int x,int y){return dis[x]+dis[y]-2ll*dis[lca(x,y)];}
data merge(int a,int b,int c,int d)
{
static int tmp[5];
tmp[0]=a;tmp[1]=b;tmp[2]=c;tmp[3]=d;
int res1=a,res2=b;ll res=0;
for(int i=0;i<4;++i) for(int j=i+1;j<4;++j)
{
ll t=getdis(tmp[i],tmp[j]);
if(t>res) res=t,res1=tmp[i],res2=tmp[j];
}
return data(res1,res2);
}
int findf(int x){return f[x]==x?x:f[x]=findf(f[x]);}
}
using namespace Tree;
namespace DreamLolita
{
int n,a[N];
ll ans;
vector<int>G[N];
void clear()
{
for(int i=1;i<=n;++i)head[i]=0;
ans=0;ind=0;tot=1;
}
bool cmp(int x,int y){return E[x].w>E[y].w;}
void solve(int now)
{
if(!G[now].size()) return;
sort(G[now].begin(),G[now].end(),cmp);
for(auto id:G[now])
{
int u=E[id].u,v=E[id].v;
f[u]=u;f[v]=v;d[u]=data(u,u);d[v]=data(v,v);
}
for(auto id:G[now])
{
int u=E[id].u,v=E[id].v,w=E[id].w;
u=findf(u),v=findf(v);
f[u]=v;d[v]=merge(d[v].x,d[v].y,d[u].x,d[u].y);
ans=max(ans,1ll*getdis(d[v].x,d[v].y)*w*now);
}
G[now].clear();
}
int gcd(int x,int y){return y?gcd(y,x%y):x;}
void addall(int x,int id)
{
for(int i=1;1ll*i*i<=x;++i) if(!(x%i))
{
G[i].pb(id);
if(i!=x/i) G[x/i].pb(id);
}
}
void solution()
{
n=read();
for(int i=1;i<=n;++i) a[i]=read();
for(int i=1;i<n;++i)
{
int u=read(),v=read(),w=read();
add(u,v,w);E[i]=edge(u,v,min(a[u],a[v]));addall(gcd(a[u],a[v]),i);
}
dfs(1);initst();
for(int i=1;i<M;++i) solve(i);
printf("%lld\n",ans); clear();
}
void init()
{
fc[0]=1;for(int i=1;i<20;++i)fc[i]=fc[i-1]<<1;
for(int i=2;i<N*2;++i) Log[i]=Log[i>>1]+1;
}
}
int main()
{
#ifdef Durant_Lee
freopen("CC_MXPATH.in","r",stdin);
freopen("CC_MXPATH.out","w",stdout);
#endif
DreamLolita::init();
int T=read();
while(T--) DreamLolita::solution();
return 0;
}