BZOJ 3522 DFS+DP

2019-11-06 07:29:38

字体：大中小

来源：转载

供稿：网友

思路： f[]表示选1个点的 g[]表示选2个点的 dp一下

ans+=(ll)g[k]*deep[k]; g[k]+=(ll)f[k]*deep[k]; f[k]+=deep[k];

听说有O(n)做法但是我不会

//By SiriusRen#include <cstdio>#include <cstring>using namespace std;const int N=10050;int n,xx,yy,first[N],next[N],v[N],tot,deep[N],f[N],g[N];long long ans;typedef long long ll;void add(int x,int y){v[tot]=y,next[tot]=first[x],first[x]=tot++;}void dfs(int x,int fa,int dep){ deep[dep]++; for(int i=first[x];~i;i=next[i]) if(v[i]!=fa)dfs(v[i],x,dep+1);}int main(){ memset(first,-1,sizeof(first)); scanf("%d",&n); for(int i=1;i!=n;i++){ scanf("%d%d",&xx,&yy); add(xx,yy),add(yy,xx); } for(int i=1;i<=n;i++){ memset(f,0,sizeof(f)),memset(g,0,sizeof(g)); for(int j=first[i];~j;j=next[j]){ memset(deep,0,sizeof(deep)); dfs(v[j],i,1); for(int k=1;k<=n;k++){ ans+=(ll)g[k]*deep[k]; g[k]+=(ll)f[k]*deep[k]; f[k]+=deep[k]; } } } PRintf("%lld/n",ans);}

上一篇：【剑指offer】面试题12：打印1到最大的n位数

下一篇：JVM学习笔记——虚拟机类加载机制