Never or now.
本文从WordPress迁移而来, 查看全部WordPress迁移文章
树dp 树的重心
简单题,找树的重心,有多个重心,输出标号较小的,另外输出重心下最大分支的节点数
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859
#include <iostream>#include <cstdio>#include <cstring>#include <vector>using namespace std;#define N 20010#define INF 0x3f3f3f3f#define cl(xx,yy) memset((xx),(yy),sizeof((xx)))#define pb push_backvector<int>e[N];int n,cnt[N],Max[N],root,ans;void dfs(int u,int fa){ cnt[u] = 1; for(int i = 0; i < e[u].size(); i++){ int v = e[u][i]; if(v == fa) continue; dfs(v,u); cnt[u] += cnt[v]; Max[u] = max(Max[u],cnt[v]); }}void find(int u,int fa){ int tmp = cnt[1] - cnt[u]; tmp = max(tmp,Max[u]); if(tmp < ans){ ans = tmp; root = u; } else if(tmp == ans && u < root){ ans = tmp; root = u; } for(int i = 0; i < e[u].size(); i++){ int v = e[u][i]; if(v == fa) continue; find(v,u); }}int main(){ int T; scanf("%d",&T); while(T--){ scanf("%d",&n); for(int i = 1; i <= n; i++) e[i].clear(); for(int i = 1; i < n; i++){ int u,v; scanf("%d%d",&u,&v); e[u].pb(v); e[v].pb(u); } cl(Max,0); root = -1; ans = INF; dfs(1,-1); find(1,-1); printf("%d %d\n",root,ans); } return 0;}