题意: 给出两棵无根树 问选择两个点使得两棵树相连 使得树上每对点的距离和最小
队友解法:
找出重心 方法:最大"子树"(也包括上面的树)最小化 也就是树上每个点将树分为两部分 这两部分的差值最小 那么该点就是重心
#include "bits/stdc++.h" #define pb push_back #define ls l,m,now<<1 #define rs m+1,r,now<<1|1 #define hhh printf("hhh ") #define see(x) (cerr<<(#x)<<'='<<(x)<<endl) using namespace std; typedef long long ll; typedef pair<int,int> pr; inline int read() {int x=0;char c=getchar();while(c<'0'||c>'9')c=getchar();while(c>='0'&&c<='9')x=(x<<3)+x*2+c-'0',c=getchar();return x;} const int maxn = 1e5+10; const int mod = 1e9+7; const double eps = 1e-9; int head[maxn], nxt[maxn<<2], to[maxn<<2], tot; int n; bool vis[maxn]; inline void add_edge(int u, int v) { ++tot, to[tot]=v, nxt[tot]=head[u], head[u]=tot; ++tot, to[tot]=u, nxt[tot]=head[v], head[v]=tot; } int minu[2], size[maxn], minBalance[2]; int root[2], N[2]; void dfs(int u, int f) { vis[u]=1; if(!f) { if(root[0]) root[1]=u; else root[0]=u; } size[u]=1; for(int i=head[u]; i; i=nxt[i]) { int v=to[i]; if(v!=f) { dfs(v,u); size[u]+=size[v]; } } } void dfs1(int u, int fa, int f) { int maxSubTree=0; for(int i=head[u]; i; i=nxt[i]) { int v=to[i]; if(v!=fa) { dfs1(v,u,f); maxSubTree=max(maxSubTree,size[v]); } } maxSubTree=max(maxSubTree,N[f]-size[u]); if(maxSubTree<minBalance[f]) { minBalance[f]=maxSubTree; minu[f]=u; } } ll ans=0; void dfs2(int u, int f) { size[u]=1; for(int i=head[u]; i; i=nxt[i]) { int v=to[i]; if(v!=f) { dfs2(v,u); ans+=1LL*size[v]*(n-size[v]); size[u]+=size[v]; } } } int main() { //ios::sync_with_stdio(false); n=read(); for(int i=0; i<n-2; ++i) add_edge(read(),read()); for(int i=1; i<=n; ++i) { if(!vis[i]) dfs(i,0); } //see(root[0]); //see(root[1]); N[0]=size[root[0]], N[1]=size[root[1]]; //see(N[0]); //see(N[1]); minBalance[0]=minBalance[1]=2e9; dfs1(root[0],0,0); dfs1(root[1],0,1); add_edge(minu[0],minu[1]); //printf("%d %d ", minu[0], minu[1]); dfs2(1,0); cout<<ans<<endl; }
还可以dfs求出每个点到树上其他所有点的距离之和 最小的显然为重心
具体求距离和方法:
换根法
void dfs(int u,int fa) { sz[u] = 1; dep[u] = dep[fa]+1; for(int i = p[u];i+1;i=e[i].next) { int v = e[i].v; if(v==fa) continue; dfs(v,u); sz[u]+=sz[v]; } } void dfs_(int u,int fa) { if(u!=1) ans[u] = ans[fa] + n - 2ll*sz[u]; for(int i = p[u];i+1;i=e[i].next) { int v = e[i].v; if(v==fa) continue; dfs_(v,u); } } int main() { //ios::sync_with_stdio(false); //freopen("a.txt","r",stdin); //freopen("b.txt","w",stdout); int a,b; scanf("%d",&n); init(); for(int i = 1;i<n;++i) { scanf("%d%d",&a,&b); add(a,b); add(b,a); } dfs(1,0); ll now = 0; for(int i = 2;i<=n;++i) now+=dep[i] - dep[1]; ans[1] = now; dfs_(1,0); for(int i = 1;i<=n;++i) printf("%lld ",ans[i]); //fclose(stdin); //fclose(stdout); //cout << "time: " << (long long)clock() * 1000 / CLOCKS_PER_SEC << " ms" << endl; return 0; }