POJ 3417 Network

题意：给你一颗N个节点树，再给你M条新边（保证不与树边重复）。现在求剪短一条树边和任意M边中的一条边，能将树分成两个联通块的方案

> N (1 ≤ N ≤ 100 000), M (1 ≤ M ≤ 100 000)

一开始想的：暴力,N*M然后检验。。

然后想到树形DP，能不能按照每个节点剪掉它与它父亲节点的树边思考

剪掉这条树边，树边部分肯定不与大树相连接

分类讨论一下新边：

1.如果该子树内任意节点不与大树有新边，那么剪掉任意一条新边都可以产生两个联通块，方案数+M

2.如果该子树内有且仅有1个节点与大树有新边，那么剪掉该边即可产生两个联通块，方案数+1

3.如果该子树内有2个或以上节点与大树有新边，不可能的

问题就是怎么算每一个子树内与树外连接的新边数量

我们发现，两个节点在同子树内，且子树根结点离根节点最远时（最小子树），那么该节点必是两个节点的lca。

设a[i]为以i为根结点连接子树外的新边数量

所以每次连新边的时候，a[x]++,a[y]++,a[lca(x,y)]-=2

然后dfs把每个子树累加

CODE:

#include<iostream>
#include<cstdio>
typedef long long ll;
const int N = 100100;
struct edge{
    int next,to;
}e[N<<1];
int last[N],top[N],m,size[N],wson[N],D[N],fa[N];
int cnt;ll dp[N];ll ans=0;
inline void add(int a,int b){
    cnt++;
    e[cnt].to=b;e[cnt].next=last[a],last[a]=cnt;
}
inline int read(){
    int x=0,flag=1;char c=getchar();
    while(!isdigit(c)){if(c=='-')flag*=-1;c=getchar();}
    while(isdigit(c)){x=(x<<3)+(x<<1)+c-'0';c=getchar();}
    return x*flag;
}
inline int dfs1(int x,int f){
    size[x]=1;
    D[x]=D[f]+1;
    fa[x]=f; 
    for(int i=last[x];i;i=e[i].next){
        if(e[i].to==f) continue;
        dfs1(e[i].to,x);
        size[x]+=size[e[i].to]; 
        if(size[e[i].to]>size[wson[x]]) wson[x]=e[i].to;
    }
    return 0;
}
inline int dfs2(int x,int topf){
    top[x]=topf;
    if(!wson[x]) return 0;
    dfs2(wson[x],topf);
    for(int i=last[x];i;i=e[i].next){
        if(e[i].to==fa[x]) continue;
        if(e[i].to==wson[x]) continue;
        dfs2(e[i].to,e[i].to);
    }
    return 0;
}
inline int lca(int x,int y){
    while(top[x]!=top[y]){
        if(D[top[x]]<D[top[y]]) std::swap(x,y);
        x=fa[top[x]];
    }
    return D[x]>D[y]?y:x;
}
inline int dfs(int x){
    for(int i=last[x];i;i=e[i].next){
        if(e[i].to==fa[x]) continue;
        dfs(e[i].to);
        dp[x]+=dp[e[i].to];
    }
    if(!dp[x]&&fa[x]) ans+=m; 
    if(dp[x]==1) ans++;
    return 0;
}
int main(){
    int n=read();m=read();
    for(int i=1;i<=n-1;++i){
        int x=read(),y=read();
        add(x,y),add(y,x);
    }
    dfs1(1,0);
    dfs2(1,1);
    for(int i=1;i<=m;++i){
        int a=read(),b=read();
        int LCA=lca(a,b);
        dp[a]++,dp[b]++,dp[LCA]-=2;
    }
    dfs(1);
    printf("%lld",ans);
    return 0;
}