首页 > 代码库 > HDU_4912 Path on the tree 2014多校5 贪心+LCA
HDU_4912 Path on the tree 2014多校5 贪心+LCA
当时刚学LCA-tarjan不久,就比赛有这个题,但没想到还是没做出来。。一开始以为是DP来着,没想到是贪心,想想也对,从树的最下层开始,每次遇到询问的点,就找到他们的LCA(路径里面必经LCA),然后把该LCA下的子树连同自己全部染色为不可用了。
#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <vector>#include <queue>using namespace std;const int N = (100000+10)*2;int u[N],v[N],ft[N],nt[N],cnt;int dep[N];vector<int> G[N];void add(int a,int b){ u[cnt]=a; v[cnt]=b; nt[cnt]=ft[a]; ft[a]=cnt++;}int f[N];int anc[N];int vis[N],col[N];struct edge{ int a,b,anc,dep; bool operator < (const edge& rhs) const{ return dep>rhs.dep; }}E[N];int findset(int x){ if (x!=f[x]){ f[x]=findset(f[x]); } return f[x];}int unionset(int a,int b){ int r1=findset(a); int r2=findset(b); if (r1==r2) return r1; f[r2]=r1; return r1;}void tarjan(int x,int fa){ anc[x]=x; for (int i=ft[x];i!=-1;i=nt[i]){ int nx=v[i]; if (nx==fa) continue; tarjan(nx,x); int rt=unionset(x,nx); anc[rt]=x; } col[x]=1; for (int i=0;i<G[x].size();i++){ int ii=G[x][i]; int nx=E[ii].a^E[ii].b^x; if (col[nx]){ E[ii].anc=findset(nx); E[ii].dep=dep[E[ii].anc]; } }}void dfs1(int x,int fa,int d){ dep[x]=d; for (int i=ft[x];i!=-1;i=nt[i]){ int vx=v[i]; if (vx==fa) continue; dfs1(vx,x,d+1); }}void dfs2(int x){ vis[x]=1; for (int i=ft[x];i!=-1;i=nt[i]){ int vx=v[i]; if (dep[vx]<dep[x] || vis[vx]) continue; dfs2(vx); }}int main(){ int n,m,a,b; while (scanf("%d%d",&n,&m)!=EOF) { memset(ft,-1,sizeof(ft)); memset(vis,0,sizeof(vis)); memset(col,0,sizeof(col)); cnt=0; for (int i=1;i<n;i++){ scanf("%d%d",&a,&b); add(a,b); add(b,a); G[i].clear(); f[i]=i; } dfs1(1,-1,0); G[n].clear(); f[n]=n; for (int i=0;i<m;i++){ scanf("%d%d",&a,&b); G[a].push_back(i); G[b].push_back(i); E[i].a=a; E[i].b=b; } tarjan(1,-1); sort(E,E+m); int ans=0; for (int i=0;i<m;i++){ if (!vis[E[i].a] && !vis[E[i].b]){ ans++; dfs2(E[i].anc); } } printf("%d\n",ans); } return 0;}
HDU_4912 Path on the tree 2014多校5 贪心+LCA
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。