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 \times 10^5\)， \(1 \le u,v \le n\)， \(w \le 10^6\)。

---

蜜汁题目。

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

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

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

复杂度同阶

---

Code:

#include 
    
     #include 
     
      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 
      
        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
       
        w?mx:w;    }    for(int i=1;i<=mx;i++)    {        for(int j=i;j<=mx;j+=i)            for(int k=0;k
       
      
     
    

---

2018.10.11