首页 > 代码库 > 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