n=int(input()) g=[[] for _ in range(n+1)] for _ in range(n-1): u,v=map(int,input().split()) g[u].append(v) g[v].append(u) s=[0]*(n+1) dep=[0]*(n+1) def dfs1(u,f): s[u]=1 for v in g[u]: if v==f:continue dfs1(v,u) s[u]+=s[v] def dfs2(u,f): dep[u]=dep[f]+1 for v in g[u]: if v==f:continue dfs2(v,u) dfs2(1,0) ans=0 for i in range(1,n+1):ans=max(ans,dep[i]) p=dep.index(ans) dfs1(p,0) print(sum(s))
最近在学树形dp,先用换根过掉了,但是在思考的过程中想到一种比较奇妙的想法:先找到深度最大的节点,也就是祖先。然后以祖先为根节点开始暴力求整棵树的子树和。但是这样的做法只能得60分,很好奇到底是哪里出问题了,希望有人hack我一下!!!!
全部评论
(0) 回帖