随机游走

#include<bits/stdc++.h>
#define ll long long
using namespace std;
struct Edge
{
int to;
int next;
}e[200005];
int n,m,edgenum,head[100005],d[100005],pa[100005];
ll f[100005],g[100005],ans,maxup[100005],maxdown[100005];
ll tmp[100005],top,max1[100005],max2[100005],tmp2[100005];
void add(int u,int v)
{
e[++edgenum].to=v;
e[edgenum].next=head[u];
head[u]=edgenum;
}
void dfs_f(int node)
{
for(int hd=head[node];hd;hd=e[hd].next)
{
int to=e[hd].to;
if(to==pa[node])continue;
pa[to]=node;
dfs_f(to);
f[node]+=f[to];
}
f[node]+=d[node];
}
void dfs_g(int node)
{
if(node!=1)g[node]=g[pa[node]]+f[pa[node]]-f[node];
for(int hd=head[node];hd;hd=e[hd].next)
{
int to=e[hd].to;
if(to==pa[node])continue;
dfs_g(to);
}
}
void dfs_tot(int node)
{
for(int hd=head[node];hd;hd=e[hd].next)
{
int to=e[hd].to;
if(to==pa[node])continue;
dfs_tot(to);
maxup[node]=max(maxup[node],maxup[to]+f[to]);
maxdown[node]=max(maxdown[node],maxdown[to]+g[to]);
}
top=0;
for(int hd=head[node];hd;hd=e[hd].next)
{
int to=e[hd].to;
if(to==pa[node])continue;
tmp[++top]=maxup[to]+f[to];
tmp2[top]=maxdown[to]+g[to];
}
for(int i=1;i<=top;i++)
max1[i]=max(max1[i-1],tmp[i]);
max2[top+1]=0;
for(int i=top;i>=1;i--)
max2[i]=max(max2[i+1],tmp[i]);
for(int i=1;i<=top;i++)
ans=max(ans,tmp2[i]+max(max1[i-1],max2[i+1]));
}
int main()
{
scanf("%d",&n);
for(int i=1;i<n;i++)
{
int u,v;
scanf("%d%d",&u,&v);
add(u,v);
add(v,u);
d[u]++;
d[v]++;
}
dfs_f(1);
dfs_g(1);
dfs_tot(1);
printf("%lld.00000n",ans);
return 0;
}

来源：zr

最后

以上就是动人发卡为你收集整理的随机游走的全部内容，希望文章能够帮你解决随机游走所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。