题意:求树的重心
题解:先跑一遍dfs 预处理出这种遍历方式每个节点的儿子(含自己)的数
再跑一遍 每个点的值就是他所有儿子中取一个最大值 再和它父亲这个方向比较一下
又被卡常了 vector一直tle 需要用前向星....
#include#include #include #include #include using namespace std;int read(){ int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){ if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f;}struct node{ int no, to, nex;}E[100005];int n, rt;int du[50005];int head[50005];int son[50005];int dp[50005];int dfs1(int x, int fa){ son[x] = 1; int c = head[x]; for(int i = c; i; i = E[i].nex) { int c = E[i].to; if(c == fa) continue; son[x] += dfs1(c, x); } return son[x];}void dfs2(int x, int fa){ dp[x] = n - son[x]; int c = head[x]; for(int i = c; i; i = E[i].nex) { int c = E[i].to; if(c == fa) continue; dp[x] = max(dp[x], son[c]); dfs2(c, x); }}int main(){ while(~scanf("%d", &n)) { for(int i = 1; i <= n; i++) du[i] = son[i] = dp[i] = head[i] = 0; int cn = 0; for(int i = 1; i < n; i++) { int u, v; u = read(); v = read(); E[++cn].no = u; E[cn].to = v; E[cn].nex = head[u]; head[u] = cn; E[++cn].no = v; E[cn].to = u; E[cn].nex = head[v]; head[v] = cn; du[u]++; du[v]++; } for(int i = 1; i <= n; i++) if(du[i] == 1) { rt = i; break; } int o = dfs1(rt, -1); dfs2(rt, -1); int ans = n + 5; int cnt = 0; for(int i = 1; i <= n; i++) ans = min(ans, dp[i]); for(int i = 1; i <= n; i++) if(dp[i] == ans) cnt++; for(int i = 1; i <= n; i++) { if(dp[i] == ans) { if(cnt == 1) { printf("%d\n", i); break; } else printf("%d ", i); cnt--; } } } return 0;}