Description

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

Hint

对于 30%的数据,n≤1000n\leq 1000

对于额外 30%的数据,w≤100w\leq100

对于 100%的数据,n≤4∗105,1≤u,v≤n,w≤106n\leq 4 * 10^5,1\leq u,v\leq n,w\leq 10^6

Solution

首先考虑w比较小的做法，我们可以枚举公因数，然后每次O(n)O(n)去加边并dfs一遍求出最长链

这样的复杂度是O(w∗n)O(w * n)的

而实际上我们并不需要在枚举公因数时，每一个点和每一条边都判断一下。

考虑用空间换时间，把每条边拆成它因数个数条边，然后每次枚举了公因数后直接便利那些边和点即可。

那么这样的复杂度是所有数的质因子个数，最多不会超过O(n1.5)O(n^{1.5})

要注意数组不能memset，要手动清空

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
#include <bits/stdc++.h>
#define pb(x) push_back(x)

using namespace std;

const int Maxn = 4 * 1e5 + 100;

int e, Begin[Maxn], To[Maxn << 1], Next[Maxn << 1], W[Maxn << 1];

int Stack[Maxn << 2], top;

int N;

inline void add_edge (int x, int y, int z)
{
    To[++e] = y;
    Next[e] = Begin[x];
    Begin[x] = e;
    W[e] = z;
    Stack[++top] = x;
    Stack[++top] = y;
}

int Ans[Maxn];

struct node
{
    int x, y, z;
}E[Maxn << 1];

vector <int> vec[1000010];

int now[Maxn], maxdep[Maxn], Vis[Maxn], ma[Maxn];
int Vis1[Maxn];
int cnt;

inline void dfs (int s, int x, int fa, int dep)
{
    Vis[x] = cnt;
    if (dep >= maxdep[s]) maxdep[s] = dep, now[s] = x;
    for (int i = Begin[x]; i; i = Next[i])
    {
        int y = To[i];
        if (y == fa) continue;
        dfs(s, y, x, dep + 1);
    }
}

int Maxdep;

inline void dfs1 (int x, int fa, int dep)
{
    Vis1[x] = 1;
    if (dep >= Maxdep) Maxdep = dep;
    for (int i = Begin[x]; i; i = Next[i])
    {
        int y = To[i];
        if (y == fa) continue;
        dfs1(y, x, dep + 1);
    }
}

int main()
{
    freopen("walk.in", "r", stdin);
    freopen("walk.out", "w", stdout);
    scanf("%d", &N);
    for (int i = 1; i < N; ++i)
    {
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        E[i] = (node){x, y, z};
        for (int j = 1; j * j <= z; ++j)
        {
            if (!(z % j))
            {
                vec[j].pb(i);
                if (j * j != z)
                    vec[z / j].pb(i);
            }
        }
    }
    for (int i = 1; i <= 1000000; ++i)
    {
        e = cnt = 0;
        for (int j = 0; j < vec[i].size(); ++j)
        {
            add_edge (E[vec[i][j]].x, E[vec[i][j]].y, E[vec[i][j]].z),add_edge (E[vec[i][j]].y, E[vec[i][j]].x, E[vec[i][j]].z);
        }
        for (int j = 1; j <= top; ++j)
            if (!Vis[Stack[j]])
            {
                ++cnt;
                dfs(Stack[j], Stack[j], 0, 0);
                ma[cnt] = now[Stack[j]];
            }
        Maxdep = 0;
        for (int j = 1; j <= top; ++j)
            if (!Vis1[ma[Vis[Stack[j]]]])
                dfs1(ma[Vis[Stack[j]]], 0, 0);
        while (top) Begin[Stack[top]] = Vis[Stack[top]] = Vis1[Stack[top]] = maxdep[Stack[top]] = now[Stack[top]] = 0, top--;
        Ans[Maxdep] = i;
    }
    for (int i = N; i >= 1; --i) Ans[i] = max(Ans[i], Ans[i + 1]);
    for (int i = 1; i <= N; ++i) printf("%d\n", Ans[i]);
    return 0;
}