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

题目大意

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

---

题目分析

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

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

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

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

---

代码

#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;
}