隐藏
「十连赛NOIPday5」树 - 树形动规+约数 | Bill Yang's Blog

路终会有尽头,但视野总能看到更远的地方。

0%

「十连赛NOIPday5」树 - 树形动规+约数

题目大意

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


题目分析

这道题第一眼看成了点分治,然后开始思考如何处理$i$个询问。
嗯?这不是点分治+FFT。
正当我准备开始写的时候,我才发现最大公约数不具有最优合并性。
两个最大公约数合起来说不定更小。

那怎么办呢?岂不是不可做?实际上是可以做的,思路非常有借鉴意义。

我们枚举答案$ans$,表示最大公约数为它,然后在树上只走$ans$的倍数的边。

但是这样依然要超时,怎么办呢?加一个玄学优化,用一个链表$list[i][]$存下来是$i$倍数的边,然后每次重新加边即可。
时间复杂度约$O(n\sqrt{w})$。


代码

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
#include<iostream>
#include<vector>
#include<cmath>
using namespace std;
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
int max(int a,int b) {
if(a>b)return a;
return b;
}
const int maxn=400005;
vector<int>edges[maxn],Value[1000005];
struct Edge {
int from,to,dist;
} edge[maxn];
int f1[maxn],f2[maxn],f[maxn],vst[maxn],ans[maxn];
void Decompos(int id) {
int x=edge[id].dist;
for(int i=1; i<=sqrt(x); i++) {
if(x%i==0) {
Value[i].push_back(id);
if(x/i!=i)Value[x/i].push_back(id);
}
}
}
void TreeDp(int Now,int father,int id) {
vst[Now]=id;
f[Now]=f1[Now]=f2[Now]=0;
for(auto &Next:edges[Now]) {
if(Next==father)continue;
TreeDp(Next,Now,id);
if(f1[Next]+1>f1[Now]) {
f2[Now]=f1[Now];
f1[Now]=f1[Next]+1;
} else if(f1[Next]+1>f2[Now])f2[Now]=f1[Next]+1;
f[Now]=max(f[Now],f[Next]);
}
f[Now]=max(f[Now],f1[Now]+f2[Now]);
}
int n,Max=0;
void AddEdge(int x,int y) {
edges[x].push_back(y);
}
int main() {
n=Get_Int();
for(int i=1; i<n; i++) {
edge[i].from=Get_Int();
edge[i].to=Get_Int();
edge[i].dist=Get_Int();
Max=max(Max,edge[i].dist);
Decompos(i);
}
for(int i=1; i<=Max; i++) {
int len=0;
for(auto &k:Value[i]) {
Edge& e=edge[k];
AddEdge(e.from,e.to);
AddEdge(e.to,e.from);
}
for(auto &k:Value[i]) {
Edge& e=edge[k];
if(vst[e.from]!=i) {
TreeDp(e.from,0,i);
len=max(len,f[e.from]);
}
}
ans[len]=i;
for(auto &k:Value[i]) {
Edge& e=edge[k];
edges[e.from].clear();
edges[e.to].clear();
}
}
for(int i=n-1; 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;
}
姥爷们赏瓶冰阔落吧~