[LUOGU] P3128 [USACO15DEC]最大流Max Flow

题意：一棵树，多次给指定链上的节点加1，问最大节点权值

n个点，n-1条边很容易惯性想成一条链，幸好有样例..

简单的树剖即可！（划去）

正常思路是树上差分，毕竟它就询问一次..

#include<iostream>

#include<cstring>

#include<cstdio>

using namespace std;

inline int rd(){

    int ret=,f=;char c;

    while(c=getchar(),!isdigit(c))f=c=='-'?-:;

    while(isdigit(c))ret=ret*+c-'',c=getchar();

    return ret*f;

}

const int MAXN=<<;

struct Edge{

    int next,to;

    Edge(int x=,int

    y=){next=x;to=y;}

}e[MAXN];

int ecnt,head[MAXN];

inline void add(int x,int y){

    e[++ecnt]=Edge(head[x],y);

    head[x]=ecnt;

}

int n,m;

int fa[MAXN],dep[MAXN],siz[MAXN],hs[MAXN];

void dfs1(int x,int pre){

    fa[x]=pre;dep[x]=dep[pre]+;siz[x]=;

    int mx=,tmp=;

    for(int i=head[x];i;i=e[i].next){

        int v=e[i].to;

        if(v==pre) continue;

        dfs1(v,x);

        siz[x]+=siz[v];

        if(siz[v]>mx){mx=siz[v];tmp=v;}

    }

    hs[x]=tmp;

}

int top[MAXN],id[MAXN],tot;

void dfs2(int x,int tp){

    top[x]=tp;id[x]=++tot;

    if(hs[x]) dfs2(hs[x],tp);

    for(int i=head[x];i;i=e[i].next){

        int v=e[i].to;

        if(v==fa[x]||v==hs[x]) continue;

        dfs2(v,v);

    }

}

int lca(int x,int y){

    int ret;

    while(top[x]!=top[y]){

        dep[top[x]]>dep[top[y]]?x=fa[top[x]]:y=fa[top[y]];

    }

    return dep[x]<dep[y]?x:y;

}

int ans,sum[MAXN];

void dfs(int cur){

    for(int i=head[cur];i;i=e[i].next){

        int v=e[i].to;

        if(v==fa[cur]) continue;

        dfs(v);

        sum[cur]+=sum[v];

    }

    ans=max(sum[cur],ans);

}

int main(){

    n=rd();m=rd();

    int x,y,t;

    for(int i=;i<=n-;i++){

        x=rd();y=rd();

        add(x,y);add(y,x);

    }

    dfs1(,);

    dfs2(,);

    for(int i=;i<=m;i++){

        x=rd();y=rd();t=lca(x,y);

        sum[x]+=;sum[y]+=;

        sum[t]-=;sum[fa[t]]-=;

    }

    dfs();

    cout<<ans<<endl;

    return ;

}

树上差分

#include<iostream>

#include<cstring>

#include<cstdio>

using namespace std;

inline int rd(){

    int ret=,f=;char c;

    while(c=getchar(),!isdigit(c))f=c=='-'?-:;

    while(isdigit(c))ret=ret*+c-'',c=getchar();

    return ret*f;

}

const int MAXN=<<;

struct Edge{

    int next,to;

    Edge(int x=,int

    y=){next=x;to=y;}

}e[MAXN];

int ecnt,head[MAXN];

inline void add(int x,int y){

    e[++ecnt]=Edge(head[x],y);

    head[x]=ecnt;

}

int n,m;

struct Seg{

    #define ls (cur<<1)

    #define rs (cur<<1|1)

    #define mid (l+r>>1)

    int mx[MAXN],add[MAXN];

    Seg(){memset(mx,,sizeof(mx));memset(add,,sizeof(add));}

    void pushup(int cur){

        mx[cur]=max(mx[ls],mx[rs]);

    }

    void pushdown(int cur,int l,int r){

        int v=add[cur];

        add[ls]+=v;add[rs]+=v;

        mx[ls]+=v;mx[rs]+=v;

        add[cur]=;

    }

    void build(int cur,int l,int r){

        if(l==r) {mx[cur]=;return;}

        build(ls,l,mid);build(rs,mid+,r);

        pushup(cur);

    }

    void update(int L,int R,int cur,int l,int r,int w){

        if(L<=l&&r<=R){mx[cur]+=w;add[cur]+=w;return;}

        pushdown(cur,l,r);

        if(L<=mid) update(L,R,ls,l,mid,w);

        if(mid <R) update(L,R,rs,mid+,r,w);

        pushup(cur);

    }

}T;

int fa[MAXN],dep[MAXN],siz[MAXN],hs[MAXN];

void dfs1(int x,int pre){

    fa[x]=pre;dep[x]=dep[pre]+;siz[x]=;

    int mx=,tmp=;

    for(int i=head[x];i;i=e[i].next){

        int v=e[i].to;

        if(v==pre) continue;

        dfs1(v,x);

        siz[x]+=siz[v];

        if(siz[v]>mx){mx=siz[v];tmp=v;}

    }

    hs[x]=tmp;

}

int top[MAXN],id[MAXN],tot;

void dfs2(int x,int tp){

    top[x]=tp;id[x]=++tot;

    if(hs[x]) dfs2(hs[x],tp);

    for(int i=head[x];i;i=e[i].next){

        int v=e[i].to;

        if(v==fa[x]||v==hs[x]) continue;

        dfs2(v,v);

    }

}

void updateLink(int x,int y,int w){

    while(top[x]!=top[y]){

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

        T.update(id[top[x]],id[x],,,n,w);

        x=fa[top[x]];

    }

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

    T.update(id[x],id[y],,,n,w);

}

int main(){

    n=rd();m=rd();

    int x,y;

    for(int i=;i<=n-;i++){

        x=rd();y=rd();

        add(x,y);add(y,x);

    }

    dfs1(,);

    dfs2(,);

    T.build(,,n);

    for(int i=;i<=m;i++){

        x=rd();y=rd();

        updateLink(x,y,);

    }

    cout<<T.mx[];

    return ;

}

树剖

巴特西

[LUOGU] P3128 [USACO15DEC]最大流Max Flow

最新文章

热门文章