CodeChef Maximum Tree Path【LCA+思维】

Maximum Tree Path

【题目描述】

传送门

【题解】

我们可以枚举GCD,然后从大到小加边(加入边权为GCD的倍数的边),那么Dist就是当前的直径了,直径可以O(1)维护。
我们来算复杂度,a[i]的因子个数最多有2 * \sqrt{a[i]},所以a[i]这条边最多被处理过2*\sqrt{a[i]}次,一共有n个点,所以复杂度是O(\sum \sqrt{a[i]}))=O(n \sqrt{max_{ai}})

代码如下

#include<cstdio>
#include<cmath>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
const int MAXN=100005;
int T,cnt,tim,n,MAXA,a[MAXN],fa[MAXN],vis[MAXN],pos[MAXN<<1],lg[MAXN<<1];
struct pt{int L,R;}P[MAXN];
struct xcw{int x,y;}S[MAXN];
struct Edge{
    int tot,lnk[MAXN],nxt[MAXN<<1],son[MAXN<<1],W[MAXN<<1];
    void clean(){memset(lnk,0,sizeof(lnk));tot=0;}
    void Add(int x,int y,int w){nxt[++tot]=lnk[x];lnk[x]=tot;son[tot]=y;W[tot]=w;}
}E;
LL Ans,Ret,dst[MAXN],Sum[MAXN],cst[MAXN<<1],f[MAXN<<1][30];
vector<int> G[10005];
#include<cctype>
int read(){
    int ret=0;char ch=getchar();bool f=1;
    for(;!isdigit(ch);ch=getchar()) f^=!(ch^'-');
    for(; isdigit(ch);ch=getchar()) ret=(ret<<1)+(ret<<3)+ch-48;
    return f?ret:-ret;
}
int get(int x){return fa[x]==x?x:fa[x]=get(fa[x]);}
int gcd(int x,int y){return y==0?x:gcd(y,x%y);}
void DFS(int x,int fa){
    cst[++cnt]=Sum[x];pos[x]=cnt;
    for(int j=E.lnk[x];j;j=E.nxt[j])
    if(E.son[j]!=fa) Sum[E.son[j]]=Sum[x]+E.W[j],DFS(E.son[j],x),cst[++cnt]=Sum[x];
}
void INIT(){
    for(int i=1;i<=cnt;i++) f[i][0]=cst[i];
    for(int j=1;(1<<j)<=cnt;j++)
    for(int i=1;i<=cnt-(1<<j)+1;i++) f[i][j]=min(f[i][j-1],f[i+(1<<j-1)][j-1]);
}
LL rmq(int L,int R){
    L=pos[L],R=pos[R];
    if(L>R) swap(L,R);
    int k=lg[R-L+1];
    return min(f[L][k],f[R-(1<<k)+1][k])<<1;
}
LL Updata(int x,int y){
    if(vis[x]!=tim) vis[x]=tim,P[x].L=P[x].R=fa[x]=x,dst[x]=0;
    if(vis[y]!=tim) vis[y]=tim,P[y].L=P[y].R=fa[y]=y,dst[y]=0;

    x=get(x),y=get(y);fa[y]=x;
    int A=P[x].L,B=P[x].R;
    if(dst[x]<dst[y]) dst[x]=dst[y],A=P[y].L,B=P[y].R;

    LL t=Sum[P[x].L]+Sum[P[y].L]-rmq(P[x].L,P[y].L);
    if(t>dst[x]) dst[x]=t,A=P[x].L,B=P[y].L;

    t=Sum[P[x].L]+Sum[P[y].R]-rmq(P[x].L,P[y].R);
    if(t>dst[x]) dst[x]=t,A=P[x].L,B=P[y].R;

    t=Sum[P[x].R]+Sum[P[y].L]-rmq(P[x].R,P[y].L);
    if(t>dst[x]) dst[x]=t,A=P[x].R,B=P[y].L;

    t=Sum[P[x].R]+Sum[P[y].R]-rmq(P[x].R,P[y].R);
    if(t>dst[x]) dst[x]=t,A=P[x].R,B=P[y].R;

    P[x]=(pt){A,B};
    return dst[x];
}
int AD(int x,int id){
    for(int i=1;i*i<=x;i++)
    if(x%i==0){
        G[i].push_back(id);
        if(i*i!=x) G[x/i].push_back(id);
    }
}
bool cmp(int x,int y){return a[S[x].x]<a[S[y].x];}
void Solve(int x){
    sort(G[x].begin(),G[x].end(),cmp);++tim;Ret=0;
    for(int i=G[x].size()-1;i>=0;i--){
        int Now=G[x][i];
        Ret=max(Ret,Updata(S[Now].x,S[Now].y));
        Ans=max(Ans,Ret*x*a[S[Now].x]);
    }
}
int main(){
    for(T=read();T;T--){
        n=read();E.clean();cnt=Ans=tim=0;MAXA=0;
        for(int i=1;i<=n;i++) MAXA=max(a[i]=read(),MAXA),vis[i]=0;
        for(int i=1,x,y,w;i<n;i++){
            x=read(),y=read(),w=read(),E.Add(x,y,w),E.Add(y,x,w);
            if(a[x]>a[y]) swap(x,y);
            S[i]=(xcw){x,y};AD(gcd(a[x],a[y]),i);
        }
        DFS(1,0);INIT();
        for(int i=2;i<=cnt;i++) lg[i]=lg[i>>1]+1;
        for(int i=1;i<=MAXA;i++) Solve(i),G[i].clear();
        printf("%lld\n",Ans);
    }
    return 0;
}

发表评论

开始在上面输入您的搜索词,然后按回车进行搜索。按ESC取消。

返回顶部