[BZOJ 4390]Max Flow

danihao123 posted @ 2016年1月09日 17:45 in 题解 with tags BZOJ 树链剖分 USACO , 749 阅读

转载请注明出处：http://danihao123.is-programmer.com/

这明明不是道网络流题。

这就是道树剖题……

没有什么太难的地方，然而还是调试了几遍才过。

代码：

/**************************************************************
    Problem: 4390
    User: danihao123
    Language: C++
    Result: Accepted
    Time:3504 ms
    Memory:7252 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn=50001;
int n;
vector<int> G[maxn];
inline void Add_Edge(int x,int y){
    G[x].push_back(y);
    return;
}
// 线段树
int maxv[maxn*4],addv[maxn*4];
void maintain(int o,int L,int R){
    int lc=o*2,rc=o*2+1;
    maxv[o]=0;
    if(R>L)
        maxv[o]=max(maxv[lc],maxv[rc]);
    if(addv[o])
        maxv[o]+=addv[o];
    return;
}
int yl,yr,v;
void update(int o,int L,int R){
    if(yl<=L && R<=yr){
        addv[o]+=v;
    }else{
        int M=L+(R-L)/2;
        if(yl<=M)
            update(o*2,L,M);
        if(yr>M)
            update(o*2+1,M+1,R);
    }
    maintain(o,L,R);
    return;
}
int ql,qr,_max;
void _query_max(int o,int L,int R,int add){
    if(ql<=L && R<=qr){
        _max=max(_max,maxv[o]+add);
    }else{
        int M=L+(R-L)/2;
        if(ql<=M)
            _query_max(o*2,L,M,add+addv[o]);
        if(qr>M)
            _query_max(o*2+1,M+1,R,add+addv[o]);
    }
    return;
}
inline void change(int l,int r,int value){
    yl=l;
    yr=r;
    v=value;
    update(1,1,n);
    return;
}
inline int query_max(int l,int r){
    ql=l;
    qr=r;
    _max=-0xfffffff;
    _query_max(1,1,n,0);
    return _max;
}
bool vis[maxn];
int dep[maxn],fa[maxn],son[maxn],siz[maxn];
void dfs_1(int x,int father,int depth){
    vis[x]=true;
    dep[x]=depth;
    fa[x]=father;
    siz[x]=1;
    int temp,max_siz=0;
    for(int i=0;i<G[x].size();i++){
        temp=G[x][i];
        if(!vis[temp]){
            dfs_1(temp,x,depth+1);
            siz[x]+=siz[temp];
            if(siz[temp]>max_siz){
                max_siz=siz[temp];
                son[x]=temp;
            }
        }
    }
    return;
}
int lable=0;
int tid[maxn],top[maxn];
void dfs_2(int x,int a){
    vis[x]=true;
    top[x]=a;
    tid[x]=++lable;
    if(son[x])
        dfs_2(son[x],a);
    else
        return;
    int temp;
    for(int i=0;i<G[x].size();i++){
        temp=G[x][i];
        if(!vis[temp]){
            dfs_2(temp,temp);
        }
    }
}
void hhhh(int s,int t){
    if(top[s]==top[t]){
        if(tid[s]>tid[t])
            swap(s,t);
        change(tid[s],tid[t],1);
        return;
    }
    if(dep[top[s]]<dep[top[t]])
        swap(s,t);
    change(tid[top[s]],tid[s],1);
    hhhh(fa[top[s]],t);
    return;
}
int main(){
    register int i;
    int t1,t2,k;
    scanf("%d%d",&n,&k);    
    for(i=1;i<n;i++){
        scanf("%d%d",&t1,&t2);
        Add_Edge(t1,t2);
        Add_Edge(t2,t1);
    }
    memset(vis,0,sizeof(vis));
    memset(son,0,sizeof(son));
    dfs_1(1,0,1);
    memset(vis,0,sizeof(vis));
    dfs_2(1,1);
    for(i=0;i<k;i++){
        scanf("%d%d",&t1,&t2);
        hhhh(t1,t2);
    }
    printf("%d\n",query_max(1,n));
    return 0;
}