题意：给出若干条电话线，询问可以最多连几个房子，最小代价 题解：不难发现这个过程就是Prim算法求最小生成树的过程，用Kruskal算法同样正确。
将所有线路按代价从小到大排序，对于每条线路(a,b,c,d)(a,b,c,d)，首先把a到b路径上的点都合并到LCA，再把c到d路径上的点都合并到LCA，最后再把两个LCA合并即可。
设same[i]表示i点往上深度最大的一个和i在同一个连通块的祖先，每次沿着same跳即可。用路径压缩的并查集维护这个same即可得到优秀的复杂度。
时间复杂度O(mlogm)。
#include <cstdio> #include <cstring> #include <algorithm> #include <vector> using namespace std; #define N 100010 typedef long long ll; struct rec{ int a,b,c,d,w; void input() { scanf("%d%d%d%d%d",&a,&b,&c,&d,&w); } }l[N]; vector<int> g[N]; int fa[N][20],h[N],f[N],same[N],num[N]; ll sum[N]; int n,m,e; void dfs(int x,int pa) { fa[x][0]=pa;h[x]=h[pa]+1; for(int i=1;i<20;++i) fa[x][i]=fa[fa[x][i-1]][i-1]; int y; for(int i=0;i<g[x].size();++i) { y=g[x][i]; if(y==pa) continue; dfs(y,x); } } int lca(int x,int y) { if(h[x]<h[y]) swap(x,y); int d=h[x]-h[y]; for(int i=0;i<20;++i) if((d>>i)&1) x=fa[x][i]; if(x==y) return x; for(int i=19;i>=0;--i) if(fa[x][i]!=fa[y][i]) { x=fa[x][i];y=fa[y][i]; } return fa[x][0]; } int Find(int x) { if(f[x]==x) return x; return f[x]=Find(f[x]); } int Same(int x) { if(same[x]==x) return x; else return same[x]=Same(same[x]); } bool cmp(rec &a,rec &b) { return a.w<b.w; } void merge(int x,int y,int w) { int fx=Find(x),fy=Find(y); if(fx!=fy) { f[fx]=fy; num[fy]+=num[fx]; sum[fy]+=sum[fx]+w; } } void doing(int x,int y,int w) { while(true) { x=Same(x); if(h[x]<=h[y]) return; merge(x,fa[x][0],w); same[x]=fa[x][0]; } } void chain(int x,int y,int w) { int z=lca(x,y); doing(x,z,w);doing(y,z,w); } int main() { int ca; scanf("%d",&ca); while(ca--) { scanf("%d%d",&n,&m); for(int i=1;i<=n;++i) { f[i]=i;same[i]=i;num[i]=1;sum[i]=0;g[i].clear(); } e=0; int x,y,fx,fy,xx,yy; for(int i=1;i<n;++i) { scanf("%d%d",&x,&y); g[x].push_back(y); g[y].push_back(x); } dfs(1,0); for(int i=1;i<=m;++i) l[i].input(); sort(l+1,l+m+1,cmp); for(int i=1;i<=m;++i) { chain(l[i].a,l[i].b,l[i].w); chain(l[i].c,l[i].d,l[i].w); merge(l[i].a,l[i].c,l[i].w); } x=Find(1); printf("%d %lld\n",num[x],sum[x]); } return 0; }