poj 3417 Network 题解

题意：

　　先给出一棵树，然后再给出m条边，把这m条边连上，然后剪掉两条边，一条是原边，一条是新边，问有多少种方案能使图不连通。

思路：

　　从原边的角度看
　　　　1.树加边，一定成环，加一条(u,v)边就有u->lca->v上的边被覆盖一次
　　　　2.当一条边没被覆盖时，删去该边与任意一条新边都能使图不连通，即有m种方案
　　　　3.当一条边被覆盖1次时，删去与该边成环的新边，即有1种方案
　　　　4.当一条边被覆盖1次以上时，没有方案
　　用树形dp，dp[i]表示第i号点与其父亲相连的边被覆盖的次数。一条新边(u,v)加入则++dp[u],++dp[v],dp[lca(u,v)]-=2，计算时从叶子结点向上累加，子节点的值加到父节点上，最后每个节点上的值就是覆盖次数。

反思：

　　1.倍增求lca时不熟练。
　　2.计算时根节点不计算。

代码：

 #include<cstdio>

 const int M=;

 #define swap(x,y) t=x,x=y,y=t

 int t,cnt,ans,v[M<<],dp[M],dep[M],hea[M<<],nex[M<<],p[M][];

 int read()

 {

     int x=; char ch=getchar();

     while (ch< || ch>) ch=getchar();

     while (ch> && ch<) x=(x<<)+(x<<)+ch-,ch=getchar();

     return x;

 }

 void add(int x,int y) { v[++cnt]=y,nex[cnt]=hea[x],hea[x]=cnt; }

 void dfs(int u,int x)

 {

     dep[u]=dep[p[u][]=x]+;

     for (int i=hea[u];i;i=nex[i])

         if (v[i]^x) dfs(v[i],u);

 }

 int lca(int x,int y)

 {

     if (dep[x]<dep[y]) swap(x,y);

     for (int i=;~i;--i)

         if (dep[p[x][i]]>=dep[y]) x=p[x][i];

     if (x==y) return x;

     for (int i=;~i;--i)

         if (p[x][i]^p[y][i]) x=p[x][i],y=p[y][i];

     return p[x][];

 }

 void DFS(int u,int x)

 {

     for (int i=hea[u],y;y=v[i],i;i=nex[i])

         if (y^x) DFS(y,u),dp[u]+=dp[y];

 }

 int main()

 {

     int n=read(),m=read(),x,y,i,j;

     for (i=;i<n;++i) x=read(),y=read(),add(x,y),add(y,x);

     dfs(,);

     for (i=;i<;++i)

         for (j=;j<=n;++j)

             if (p[j][i-]) p[j][i]=p[p[j][i-]][i-];

     for (i=;i<=m;++i) ++dp[x=read()],++dp[y=read()],dp[lca(x,y)]-=;

     DFS(,);

     for (i=;i<=n;++i)

         if (!dp[i]) ans=ans+m;

         else if (dp[i]==) ++ans;

     printf("%d\n",ans);

     return ;

 }

poj 3417 Network 题解的相关教程结束。