题目概述

给出一棵带点权的树，求每个节点 $i$ 的 $max\{(a_x,a_y)|LCA(x,y)=i,x\not=y\}$ 。

解题报告

因为 $10^5$ 内质因子个数最多只有 $2^7=128$ ，所以可以检查两个不同子树中的节点共有的最大因子。

然后怎么搞？启发式合并？因为不用修改所以可以直接上Dsu on tree。

示例程序

以前Dsu on tree好像写丑了……

#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=100000,maxv=100000,maxd=128;

int n,v[maxn+5],D[maxv+5][maxd+5],si[maxn+5],SH[maxn+5],ans[maxn+5];
int E,lnk[maxn+5],nxt[maxn+5],son[maxn+5];int num[maxv+5],MAX;bool vis[maxn+5];

#define Add(x,y) (son[++E]=(y),nxt[E]=lnk[x],lnk[x]=E)
void HLD(int x){
    for (int j=(si[x]=1,lnk[x]);j;j=nxt[j]){
        HLD(son[j]);si[x]+=si[son[j]];
        if (si[son[j]]>si[SH[x]]) SH[x]=son[j];
    }
}
void Count(int x){
    for (int i=1,V=v[x],si=D[V][0];i<=si;i++) if (num[D[V][i]]) MAX=max(MAX,D[V][i]);
    for (int j=lnk[x];j;j=nxt[j]) Count(son[j]);
}
void Insert(int x,int f){
    for (int i=1,V=v[x],si=D[V][0];i<=si;i++) num[D[V][i]]+=f;
    for (int j=lnk[x];j;j=nxt[j]) Insert(son[j],f);
}
inline void Merge(int x,int f){
    MAX=-1;for (int i=1,V=v[x],si=D[V][0];i<=si;i++) if (num[D[V][i]]) MAX=max(MAX,D[V][i]);
    for (int i=1,V=v[x],si=D[V][0];i<=si;i++) num[D[V][i]]+=f;
    for (int j=lnk[x];j;j=nxt[j]) if (!vis[son[j]]) Count(son[j]),Insert(son[j],f);
}
void Solve(int x,bool fl=true){
    for (int j=lnk[x];j;j=nxt[j]) if (son[j]!=SH[x]) Solve(son[j],false);
    if (SH[x]) Solve(SH[x],true),vis[SH[x]]=true;Merge(x,1);ans[x]=MAX;
    if (SH[x]) vis[SH[x]]=false;if (!fl) Merge(x,-1);
}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    scanf("%d",&n);for (int i=2,x;i<=n;i++) scanf("%d",&x),Add(x,i);
    for (int i=1;i<=maxv;i++) for (int j=i;j<=maxv;j+=i) D[j][++D[j][0]]=i;
    for (int i=1;i<=n;i++) scanf("%d",&v[i]);HLD(1);Solve(1);
    for (int i=1;i<=n;i++) printf("%d\n",ans[i]);return 0;
}