1072. 树的最长路径
给定一棵树，树中包含 n 个结点（编号1~n）和 n−1 条无向边，每条边都有一个权值。
现在请你找到树中的一条最长路径。
换句话说，要找到一条路径，使得使得路径两端的点的距离最远。
注意：路径中可以只包含一个点。
输入格式
第一行包含整数 n。
接下来 n−1 行，每行包含三个整数 ai,bi,ci，表示点 ai 和 bi 之间存在一条权值为 ci 的边。
输出格式
输出一个整数，表示树的最长路径的长度。
数据范围
1≤n≤10000,
1≤ai,bi≤n,
−105≤ci≤105
输入样例：
6
5 1 6
1 4 5
6 3 9
2 6 8
6 1 7
输出样例：
22
树上最长链问题，链会在某个节点的两个儿子节点的最长单链连接产生，注意该问题不需要考虑通过父节点向上的路径，因为通过父节点的链被包含在父节点的最长路径中，再统计就多余了
#include<bits/stdc++.h>
using namespace std;
const int N=10010;
struct eg{
int v,c,nex;
}edge[N*2];
int head[N],cnt,ans,Maxl[N];
void addedge(int u,int v,int c){
edge[cnt]=(eg){v,c,head[u]};
head[u]=cnt++;
}
void dfs(int u,int pre){
int Max1=0,Max2=0;
for(int i=head[u];~i;i=edge[i].nex){
int v=edge[i].v, c=edge[i].c;
if(v==pre) continue;
dfs(v,u);
int t=Maxl[v]+c;
if(t>Max1) Max2=Max1,Max1=t;
else if(t>Max2) Max2=t;
}
Maxl[u]=Max1;
ans=max(ans,Max1+Max2);
}
int main(){
int n;
memset(head,-1,sizeof head);
cin>>n;
for(int i=1;i<n;++i){
int u,v,c;
cin>>u>>v>>c;
addedge(u,v,c);
addedge(v,u,c);
}
dfs(1,0);
cout<<ans<<endl;
return 0;
}
AcWing 1075. 数字转换
如果一个数 x 的约数之和 y（不包括他本身）比他本身小，那么 x 可以变成 y，y 也可以变成 x。
例如，4 可以变为 3，1 可以变为 7。
限定所有数字变换在不超过 n 的正整数范围内进行，求不断进行数字变换且不出现重复数字的最多变换步数。
输入格式
输入一个正整数 n。
输出格式
输出不断进行数字变换且不出现重复数字的最多变换步数。
数据范围
1≤n≤50000
输入样例：
7
输出样例：
3
样例解释
一种方案为：4→3→1→7。
由于每个点的约数之和是确定是，也就是说每个点只有一个父节点，那么说明这个问题的模型是树或森林，答案就是树的最长路径
先把每个点的关系预处理建边
#include<bits/stdc++.h>
using namespace std;
const int N=50010;
int h[N],idx,max1[N],max2[N],vis[N],ans;
struct eg{
int v,nex;
}e[N*2];
int calc(int x){
int res=0;
for(int i=1;i*i<=x;++i){
if(x%i==0) {
res+=i;
if(i!=x/i&&x/i!=x) res+=x/i;
}
}
return res;
}
void add(int u,int v){
e[idx]={v,h[u]};
h[u]=idx++;
}
void dfs(int u,int pre){
vis[u]=1;
for(int i=h[u];~i;i=e[i].nex){
int v=e[i].v;
if(pre==v) continue;
dfs(v,u);
if(max1[u]<max1[v]+1){
max2[u]=max1[u];
max1[u]=max1[v]+1;
}
else if(max2[u]<max1[v]+1){
max2[u]=max1[v]+1;
}
}
ans=max(ans,max1[u]+max2[u]);
}
int main(){
int n;
memset(h,-1,sizeof h);
cin>>n;
for(int i=1;i<=n;++i){
int f=calc(i);
if(f<i){
add(f,i);
add(i,f);
}
}
for(int i=1;i<=n;++i ){
if(!vis[i]) dfs(i,-1);
}
cout<<ans<<endl;
return 0;
}