如何解决双向边问题:
因为该题解只加了一个方向的边,但是可以通过求两条路径(最长路和次长路)之和,来求最大转换次数
本题只让小数连大数(sum[i]连i)
注意dfs要return d1
//若x和y可以相互转换,则x和y之间有一条边
//x的约束之和为y,若有边,则y是x的父节点
#include <iostream>
#include <cstring>
using namespace std;
const int N=50010;
int h[N],ne[N],e[N],idx;
int sum[N];
//记录叶子节点
int st[N];
int ans;
void add(int a,int b)
{
e[idx]=b;
ne[idx]=h[a];
h[a]=idx++;
}
int dfs(int u)
{
int d1=0,d2=0;
for(int i=h[u];i!=-1;i=ne[i])
{
int j=e[i];
int d=dfs(j)+1;
if(d>=d1)
{
d2=d1;
d1=d;
}
else if(d>d2)
{
d2=d;
}
}
ans=max(ans,d1+d2);
return d1;
}
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
for(int j=2;j<=n/i;j++)
{
//数i*j的约数加上i
sum[i*j]+=i;
}
}
memset(h,-1,sizeof h);
//1的所有约数之和为0,不能遍历0
for(int i=2;i<=n;i++)
{
if(i>sum[i])
{
add(sum[i],i);
st[i]=1;
}
}
for(int i=1;i<=n;i++)
{
if(!st[i])
dfs(i);
}
cout<<ans;
return 0;
}
二刷了,做一个树形dp的总结吧
基本上就是选一个点开始,往下做dfs,一般是求长度的问题(有的边可能会有权重),如树的直径等等
#include <iostream>
#include <cstring>
using namespace std;
const int N=50010;
int e[N],ne[N],idx,h[N];
int n;
int sum[N];
int st[N];
int ans;
void add(int a,int b)
{
e[idx]=b;
ne[idx]=h[a];
h[a]=idx++;
}
int dfs(int u,int fa)
{
int d1,d2;
d1=d2=0;
for(int i=h[u];i!=-1;i=ne[i])
{
int j=e[i];
if(j==fa) continue;
int d=dfs(j,u)+1;
if(d>=d1)
{
d2=d1;
d1=d;
}
else if(d>d2)
{
d2=d;
}
}
ans=max(ans,d1+d2);
return d1;
}
int main()
{
cin>>n;
memset(h,-1,sizeof h);
for(int i=1;i<=n;i++)
{
for(int j=2;j<=n/i;j++)
{
sum[i*j]+=i;
}
}
for(int i=1;i<=n;i++)
{
if(sum[i]<i)
{
add(sum[i],i);
st[i]=1;
}
}
for(int i=1;i<=n;i++)
{
if(st[i]==1)
dfs(i,-1);
}
cout<<ans;
return 0;
}
三刷了,还是不会,草。。。
本题的技巧:
1. 将无向边转化为有向边,只从小数往大数连边
2. 将求最长路径,转化为从一个约束开始最长边和次长边之和
3. 在遍历时只遍历根节点,将叶节点标为1
#include <iostream>
#include <cstring>
using namespace std;
const int N=50010;
int e[N],ne[N],idx,h[N];
int n;
int sum[N];
int st[N];
int ans;
void add(int a,int b)
{
e[idx]=b;
ne[idx]=h[a];
h[a]=idx++;
}
int dfs(int u,int fa)
{
int d1=0,d2=0;
for(int i=h[u];i!=-1;i=ne[i])
{
int j=e[i];
if(j==fa) continue;
int d=dfs(j,u)+1;
if(d>=d1) d2=d1,d1=d;
else if(d>d2) d2=d;
}
ans=max(d1+d2,ans);
return d1;
}
int main()
{
cin>>n;
memset(h,-1,sizeof h);
for(int i=1;i<=n;i++)
{
for(int j=2;j<=n/i;j++)
{
sum[i*j]+=i;
}
}
for(int i=2;i<=n;i++)
{
if(sum[i]<i)
{
add(sum[i],i);
//st[i]=1说明i是叶节点,不是根节点,下面要找根节点遍历(其实基本就是1)
st[i]=1;
}
}
for(int i=1;i<=n;i++)
{
if(!st[i])
{
dfs(i,-1);
}
}
cout<<ans;
return 0;
}