Walk 解题报告

Walk

题目描述

给定一棵 (n) 个节点的树，每条边的长度为 (1)，同时有一个权值(w)。定义一条路径的权值为路径上所有边的权值的最大公约数。现在对于任意 (i in [1,n])，求树上所有长度为 (i) 的简单路径中权值最大的是多少。如果不存在长度为 (i) 的路径，则第 (i) 行输出 (0)。

输入输出格式

输入格式

第一行，一个整数 (n)，表示树的大小。
接下来 (n-1) 行，每行三个整数 (u,v,w)，表示 (u,v) 间存在一条权值为 (w) 的边。

输出格式

对于每种长度，输出一行，表示答案。

数据范围及约定

对于 (30\%)的数据， (n le 1000)。
对于额外 (30\%)的数据， (w le 100)。
对于 (100\%)的数据， (n le 4 imes 10^5)， (1 le u,v le n)， (w le 10^6)。

蜜汁题目。

思路：枚举每个可能的(w)，建部分图。

连边要注意一下枚举的方法，不要用memset，像CDQ分治一样撤销。

约数个数大约是(n^{frac{3}{2}})的

复杂度同阶

Code:

#include <cstdio>
#include <vector>
const int N=4e5+10;
const int M=1e6+10;
int head[N],to[N<<1],Next[N<<1],sta[N<<1],cnt;
void add(int u,int v)
{
    to[++cnt]=v,Next[cnt]=head[u],head[u]=cnt,sta[cnt]=u;
}
struct node{int u,v;}t;
int n,m,mxl,mx,used[N],ans[N];
std::vector <node> e[M];
int max(int x,int y){return x>y?x:y;}
int maxdis(int now,int fa)
{
    used[now]=1;
    int mx0=0,mx1=0,d;
    for(int i=head[now];i;i=Next[i])
    {
        int v=to[i];
        if(v!=fa)
        {
            d=maxdis(v,now);
            if(d>=mx0) mx1=mx0,mx0=d;
            else if(d>mx1) mx1=d;
        }
    }
    mxl=mxl>mx0+mx1?mxl:mx0+mx1;
    return mx0+1;
}
int main()
{
    scanf("%d",&n);
    for(int w,i=1;i<n;i++)
    {
        scanf("%d%d%d",&t.u,&t.v,&w);
        e[w].push_back(t);
        mx=mx>w?mx:w;
    }
    for(int i=1;i<=mx;i++)
    {
        for(int j=i;j<=mx;j+=i)
            for(int k=0;k<e[j].size();k++)
                add(e[j][k].u,e[j][k].v),add(e[j][k].v,e[j][k].u);
        mxl=0;
        for(int j=cnt;j;j--)
            if(!used[sta[j]])
                maxdis(sta[j],0);
        ans[mxl]=i;
        for(int j=1;j<=cnt;j++) used[sta[j]]=0,head[sta[j]]=0;
        cnt=0;
    }
    for(int i=n;i;i--) ans[i]=max(ans[i+1],ans[i]);
    for(int i=1;i<=n;i++) printf("%d
",ans[i]);
    return 0;
}

2018.10.11