BZOJ4390: [Usaco2015 dec]Max Flow

Description

Farmer John has installed a new system of N−1 pipes to transport milk between the N stalls in his barn (2≤N≤50,000), conveniently numbered 1…N. Each pipe connects a pair of stalls, and all stalls are connected to each-other via paths of pipes.

FJ is pumping milk between KK pairs of stalls (1≤K≤100,000). For the iith such pair, you are told two stalls sisi and titi, endpoints of a path along which milk is being pumped at a unit rate. FJ is concerned that some stalls might end up overwhelmed with all the milk being pumped through them, since a stall can serve as a waypoint along many of the KK paths along which milk is being pumped. Please help him determine the maximum amount of milk being pumped through any stall. If milk is being pumped along a path from sisi to titi, then it counts as being pumped through the endpoint stalls sisi and titi, as well as through every stall along the path between them.

给定一棵有N个点的树，所有节点的权值都为0。

有K次操作，每次指定两个点s,t，将s到t路径上所有点的权值都加一。

请输出K次操作完毕后权值最大的那个点的权值。

Input

The first line of the input contains NN and KK.

The next N−1 lines each contain two integers x and y (x≠y，x≠y) describing a pipe between stalls x and y.

The next K lines each contain two integers ss and t describing the endpoint stalls of a path through which milk is being pumped.

Output

An integer specifying the maximum amount of milk pumped through any stall in the barn.

Sample Input

5 10
3 4
1 5
4 2
5 4
5 4
5 4
3 5
4 3
4 3
1 3
3 5
5 4
1 5
3 4

Sample Output

题解Here!

解法一：

首先想到的就是树链剖分/LCT。。。

附代码：

#include<iostream>

#include<algorithm>

#include<cstdio>

#define MAXN 50010

using namespace std;

int n,m,c=1,d=1;

int head[MAXN],deep[MAXN],son[MAXN],size[MAXN],fa[MAXN],id[MAXN],top[MAXN];

struct node1{

	int next,to;

}a[MAXN<<1];

struct node2{

	int data,c,l,r;

}b[MAXN<<2];

inline int read(){

	int date=0,w=1;char c=0;

	while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}

	while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}

	return date*w;

}

namespace ST{

	#define LSON rt<<1

	#define RSON rt<<1|1

	#define DATA(x) a[x].data

	#define SIGN(x) a[x].c

	#define LSIDE(x) a[x].l

	#define RSIDE(x) a[x].r

	#define WIDTH(x) (RSIDE(x)-LSIDE(x)+1)

	struct Segment{

		int data,c,l,r;

	}a[MAXN<<2];

	inline void pushup(int rt){

		DATA(rt)=max(DATA(LSON),DATA(RSON));

	}

	inline void pushdown(int rt){

		if(!SIGN(rt)||LSIDE(rt)==RSIDE(rt))return;

		SIGN(LSON)+=SIGN(rt);DATA(LSON)+=SIGN(rt);

		SIGN(RSON)+=SIGN(rt);DATA(RSON)+=SIGN(rt);

		SIGN(rt)=0;

	}

	void buildtree(int l,int r,int rt){

		int mid;

		LSIDE(rt)=l;

		RSIDE(rt)=r;

		if(l==r){

			DATA(rt)=0;

			return;

		}

		mid=l+r>>1;

		buildtree(l,mid,LSON);

		buildtree(mid+1,r,RSON);

		pushup(rt);

	}

	void update(int l,int r,int c,int rt){

		int mid;

		if(l<=LSIDE(rt)&&RSIDE(rt)<=r){

			SIGN(rt)+=c;DATA(rt)+=c;

			return;

		}

		pushdown(rt);

		mid=LSIDE(rt)+RSIDE(rt)>>1;

		if(l<=mid)update(l,r,c,LSON);

		if(mid<r)update(l,r,c,RSON);

		pushup(rt);

	}

	int query(int l,int r,int rt){

		int mid,ans=0;

		if(l<=LSIDE(rt)&&RSIDE(rt)<=r)return DATA(rt);

		pushdown(rt);

		mid=LSIDE(rt)+RSIDE(rt)>>1;

		if(l<=mid)ans=max(ans,query(l,r,LSON));

		if(mid<r)ans=max(ans,query(l,r,RSON));

		return ans;

	}

	void work_add(int x,int y){

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

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

			update(id[top[x]],id[x],1,1);

			x=fa[top[x]];

		}

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

		update(id[x],id[y],1,1);

		return;

	}

}

inline void add(int x,int y){

	a[c].to=y;a[c].next=head[x];head[x]=c++;

	a[c].to=x;a[c].next=head[y];head[y]=c++;

}

void dfs1(int rt){

	son[rt]=0;size[rt]=1;

	for(int i=head[rt];i;i=a[i].next){

		int will=a[i].to;

		if(!deep[will]){

			deep[will]=deep[rt]+1;

			fa[will]=rt;

			dfs1(will);

			size[rt]+=size[will];

			if(size[son[rt]]<size[will])son[rt]=will;

		}

	}

}

void dfs2(int rt,int f){

	id[rt]=d++;top[rt]=f;

	if(son[rt])dfs2(son[rt],f);

	for(int i=head[rt];i;i=a[i].next){

		int will=a[i].to;

		if(will!=fa[rt]&&will!=son[rt])

		dfs2(will,will);

	}

}

void work(){

	int x,y;

	while(m--){

		x=read();y=read();

		ST::work_add(x,y);

	}

	printf("%d\n",ST::query(1,n,1));

}

void init(){

	int x,y;

	n=read();m=read();

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

		x=read();y=read();

		add(x,y);

	}

	deep[1]=1;

	dfs1(1);

	dfs2(1,1);

	ST::buildtree(1,n,1);

}

int main(){

	init();

	work();

	return 0;

}

总耗时3244ms。

解法二：

这题可以不用在线做，那么我们就有一个很NOIP的算法——树上差分！

若操作的节点是u，v，那么只要在差分数组num[]中这样：

int lca=LCA(u,v);

num[u]++;num[v]++;

num[lca]--;num[fa[lca]]--;

最后再用一个dfs求出和：

void get_sum(int rt){

    sum[rt]=num[rt];

    for(int i=head[rt];i;i=a[i].next){

        int will=a[i].to;

        if(will==fa[rt])continue;

        get_sum(will);

        sum[rt]+=sum[will];

    }

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

}

这样，sum[]数组中就是权值了。

那个LCA我不管你怎么求，反正什么倍增啊，树剖啊什么乱七八糟的玩意搞出来就行了。。。

附代码：

#include<iostream>

#include<algorithm>

#include<cstdio>

#define MAXN 50010

using namespace std;

int n,m,c=1,ans=0;

int num[MAXN],sum[MAXN],head[MAXN],deep[MAXN],son[MAXN],size[MAXN],fa[MAXN],top[MAXN];

struct node{

	int next,to;

}a[MAXN<<1];

inline int read(){

	int date=0,w=1;char c=0;

	while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}

	while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}

	return date*w;

}

inline void add(int x,int y){

	a[c].to=y;a[c].next=head[x];head[x]=c++;

	a[c].to=x;a[c].next=head[y];head[y]=c++;

}

void dfs1(int rt){

	son[rt]=0;size[rt]=1;

	for(int i=head[rt];i;i=a[i].next){

		int will=a[i].to;

		if(!deep[will]){

			deep[will]=deep[rt]+1;

			fa[will]=rt;

			dfs1(will);

			size[rt]+=size[will];

			if(size[son[rt]]<size[will])son[rt]=will;

		}

	}

}

void dfs2(int rt,int f){

	top[rt]=f;

	if(son[rt])dfs2(son[rt],f);

	for(int i=head[rt];i;i=a[i].next){

		int will=a[i].to;

		if(will!=fa[rt]&&will!=son[rt])

		dfs2(will,will);

	}

}

int LCA(int x,int y){

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

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

        x=fa[top[x]];

    }

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

    return x;

}

void get_sum(int rt){

    sum[rt]=num[rt];

    for(int i=head[rt];i;i=a[i].next){

        int will=a[i].to;

        if(will==fa[rt])continue;

        get_sum(will);

        sum[rt]+=sum[will];

    }

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

}

void work(){

    int x,y;

    while(m--){

        x=read();y=read();

        int lca=LCA(x,y);

        num[x]++;num[y]++;num[lca]--;num[fa[lca]]--;

    }

    get_sum(1);

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

}

void init(){

    int x,y;

    n=read();m=read();

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

        x=read();y=read();

        add(x,y);

    }

    deep[1]=1;

    dfs1(1);

    dfs2(1,1);

}

int main(){

    init();

    work();

	return 0;

}

总耗时：780ms

由此，我们可以看到，树上差分的速度几乎是树剖的4倍！

在NOIP这种严重卡常的比赛中，不到万不得已，不要用两个log的算法。。。

巴特西