POJ3417 Network (闇の連鎖) 树上差分 lca

POJ3417 Network (闇の連鎖)

### 树上差分 lca

POJ3417
闇の連鎖
奇奇妙妙的树上差分
主要边是树的结构
附加边让树的结构出现环
手画可以发现
设\(xy\)为附加边，假如第一次切断了\(xy\)通过树边相连的路径
也就是破坏了环
那么第二次就必定要切断\(xy\)
那么就可以通过边差分来解决这个问题
假如\(x\)和\(y\)之间有附加边
在这两个点上记\(+1\)，表示它到它的父亲的边被覆盖
在lca处\(-2\)来差分
dfs求子树和就是当前点到父亲边的覆盖次数
1.假如覆盖次数为\(2\)证明没有办法两刀
2.假如覆盖次数为\(1\)只能切它子树的附加边
3.假如覆盖次数为\(0\)就可以切m个附加边的任意一条
注意两个OJ数据范围不一样（POJ vector会T，用G++差不多水过去）

---

代码如下：

//#pragma GCC optimize(2)
#include<cstdio>
#include<vector>
#include<map>
#include<cstring>
using namespace std;
const int maxn=100005;
struct node{
    int nxt,to;
    #define nxt(x) e[x].nxt
    #define to(x) e[x].to
}e[maxn<<1];
int id[maxn],n,m,res,head[maxn],tot,fa[maxn],lc[maxn],d[maxn],f[maxn];
inline void add(int x,int y){
    to(++tot)=y;nxt(tot)=head[x];head[x]=tot;
}
vector<int> as[maxn],as_id[maxn];
pair<int,int> q[maxn];
int find(int x){return fa[x]==x ? fa[x] : fa[x]=find(fa[x]);}
void tarjan(int x){
    id[x]=1;
    for(int i=head[x];i;i=nxt(i)){
        if(id[to(i)]) continue;
        tarjan(to(i));
        fa[to(i)]=x;
    }
    for(unsigned int i=0;i<as[x].size();i++){
        if(id[as[x][i]]==2)
            lc[as_id[x][i]]=find(as[x][i]);
    }
    id[x]=2;
}
void dfs(int x){
    id[x]=1;
    for(int i=head[x];i;i=nxt(i)){
        if(id[to(i)]) continue;
        dfs(to(i));
        f[x]+=f[to(i)];
    }
    f[x]+=d[x];
    if(!f[x]) res+=m;
    else if(f[x]==1) res+=1;
}
int main()
{
    //freopen("1.in","r",stdin);
    scanf("%d%d",&n,&m);
    for(int i=1;i<n;i++){
        int x,y;scanf("%d%d",&x,&y);add(x,y);add(y,x);
        fa[i]=i;
    }
    fa[n]=n;
    for(int i=1;i<=m;i++){
        int x,y;scanf("%d%d",&x,&y);
        if(x==y) lc[i]=x;
        as[x].push_back(y);as_id[x].push_back(i);
        as[y].push_back(x);as_id[y].push_back(i);
        q[i].first=x;q[i].second=y;
    }
    tarjan(1);
    for(int i=1;i<=m;i++){
        d[q[i].first]++;d[q[i].second]++;
        d[lc[i]]-=2;
    }
    memset(id,0,sizeof(id));
    dfs(1);
    printf("%d",res-m);//去掉1节点
    return 0;
}