HDU6073Phone Call

题目链接

题意

​ 存在一棵树，根节点为1。有 m 种方式使得树上的点连通。每种方式给出a,b,c,d,w ，表示树上 a−b 路径上的点和 c−d 路径上的点之间能够连通，连通的花费是 w <script type="math/tex" id="MathJax-Element-5">w</script> 。将相互连通的点视为新的边，那么能够构成新图，问包含根节点的联通块的最大点数和构建对应联通块的最小花费。

分析

​ 求解联通块的点数和花费，容易想到利用并查集并点使得最后之间访问根节点就可以得到答案。而对于最小花费，只要从最小花费的连通开始即可。此时的问题对于每个操作都需要查询树上的两条路径。树上路径可以用LCA快速获取，然而遍历每条路径显然是不可行的。优化路径发现利用了LCA查询路径，对于所有点来说，都是从其到其某个祖先的搜索，而树上所有点的父节点都是唯一的。考虑进行重复遍历前只要能够直接跳到深度最小的祖先就可以解决复杂度太高的问题，而这一步可以利用并查集合并完成。所以只要用两个并查集分别合并树上路径和联通块就可以在时限内解决问题了。还有不理解的地方可以参考代码进行理解。

代码

#include<iostream> #include<cstdio> #include<cstring> #include<vector> #include<algorithm> using namespace std; #define LL long long #define MAXN 100100 struct Node{ int a,b,c,d,w; }phline[MAXN]; bool cmp(Node n1,Node n2){ return n1.w<n2.w; } vector <int> g[MAXN]; int father[MAXN][20]={0}; int depth[MAXN]={0}; int n,m; bool visit[MAXN]={false}; int pa[MAXN]; int f[MAXN]; int ff[MAXN]; LL ans[MAXN]; int num[MAXN]; int root; void dfs(int u){ int i; visit[u]=true; for(i=0;i<g[u].size();i++){ int v=g[u][i]; if ( !visit[v]){ father[v][0]=u; pa[v]=u; depth[v]=depth[u]+1; dfs(v); } } }//深搜出各点的深度，存在depth中 void bz(){ int i,j; for (j=1;j<=18;j++) for (i=1;i<=n;i++) father[i][j]=father[father[i][j-1]][j-1]; }//倍增，处理father数组，详情参照上述讲解 int LCA(int u,int v) { if ( depth[u]<depth[v] ) { int temp=u; u=v; v=temp; }//保证深度大的点为u，方便操作 int dc=depth[u]-depth[v]; int i; for (i=0;i<19;i++)//值得注意的是，这里需要从零枚举 { if ( (1<<i) & dc)//一个判断，模拟一下就会很清晰 u=father[u][i]; } //上述操作先处理较深的结点，使两点深度一致 if (u==v) return u;//如果深度一样时，两个点相同，直接返回 for (i=18;i>=0;i--){ if (father[u][i]!=father[v][i])//跳2^j步不一样，就跳，否则不跳 { u=father[u][i]; v=father[v][i]; } } u=father[u][0];//上述过程做完，两点都在LCA下一层，所以走一步即可 return u; } int find(int x){ if(f[x]==x) return x; int tmp=find(f[x]); ans[tmp]+=ans[x]; ans[x]=0; num[tmp]+=num[x]; num[x]=0; return f[x]=tmp; } int find2(int x){ if(ff[x]==x) return x; return ff[x]=find2(ff[x]); } void solve(int u,int pp,int w){ int cur=find2(u),pcur=pa[cur],fpcur,fcur; while(depth[pcur]>=depth[pp]){ fpcur=find(pcur); fcur=find(cur); if(fpcur!=fcur){ f[fcur]=fpcur; ans[fpcur]+=w; num[fpcur]+=num[fcur]; num[fcur]=0; } ff[cur]=pcur; cur=pcur; pcur=pa[find2(cur)]; } } int main(){ int T,u,v; cin>>T; while(T--){ scanf("%d %d",&n,&m); for(int i=1;i<=n;++i){ f[i]=i; ff[i]=i; ans[i]=0; num[i]=1; g[i].clear(); visit[i]=0; } for(int i=1;i<n;++i){ scanf("%d %d",&u,&v); g[u].push_back(v); g[v].push_back(u); } depth[1]=1; dfs(1); bz(); for(int i=0;i<m;++i) scanf("%d %d %d %d %d",&phline[i].a,&phline[i].b,&phline[i].c,&phline[i].d,&phline[i].w); sort(phline,phline+m,cmp); for(int i=0;i<m;++i){ int ab=LCA(phline[i].a,phline[i].b),a=phline[i].a,b=phline[i].b,w=phline[i].w; solve(a,ab,w); solve(b,ab,w); int cd=LCA(phline[i].c,phline[i].d),c=phline[i].c,d=phline[i].d; solve(c,cd,w); solve(d,cd,w); int f_ab=find(ab),f_cd=find(cd); if(f_ab!=f_cd){ f[f_ab]=f_cd; ans[f_cd]+=w; num[f_cd]+=num[f_ab]; num[f_ab]=0; } } for(int i=1;i<=n;++i) find(i); printf("%d %I64d\n",num[find(1)],ans[find(1)]); } }