P3128 [USACO15DEC] Max Flow#
Problem Description#
FJ has installed N (2≤N≤50,000) pipes between the N-1 stalls in his cow barn, numbered from 1 to N. All stalls are connected by pipes.
FJ has K (1≤K≤100,000) milk transportation routes, and the i-th route transports milk from stall si to stall ti. A milk transportation route will bring one unit of transportation pressure to the stalls at its two endpoints and all the stalls in between. You need to calculate the maximum pressure among all the stalls.
Input/Output Format#
Input Format:#
The first line of the input contains N and K.
The next N-1 lines each contain two integers x and y (x≠y) describing a pipe between stalls x and y.
The next K lines each contain two integers s and t describing the endpoint stalls of a path through which milk is being pumped.
Output Format:#
An integer specifying the maximum amount of milk pumped through any stall in the barn.
Input/Output Example#
Input Example #1:
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
Output Example #1:
9
Solve#
Tree Difference template problem.
It's difficult, spent the whole afternoon on it
(How to store the tree again?)
At first, I thought it would be difficult to find the parent using the forward star. After struggling for a while, I still used the forward star.
Then I forgot about LCA. I even used Tarjan to find the LCA between every two points, and the array was too small. As a result, it TLE+MLE.
I changed to using doubling to find the LCA, but it still didn't pass the test cases. Later, I found out that I was using the array storing the parent in the Tarjan LCA...
Then the reason for only passing one or two points was:
int getLca(int p1,int p2) {
if(depth[p1]<depth[p2]){p1^=p2;p2^=p1;p1^=p2;}
for(int i=H;i>=0;--i){
if(depth[f[p1][i]]>=depth[p2])p1=f[p1][i];}
if(p1==p2)return p1;
for(int i=H;i>=0;--i)
if(f[p1][i]!=f[p2][i]){
p1=f[p1][i];
p2=f[p2][i];}
/*It's right here!!!!*/
return p1;
//It should be return f[p1][0];
}
When there was an error, I wrote two initialization methods, dfs and bfs, and now they can all pass.
The complete code is as follows:
#include<cstdio>
#include<iostream>
#include<utility>
#include<map>
#include<cstring>
#include<cmath>
using namespace std;
const int MAXN=2e5+5;
struct ed
{
int to,nex,w;
} e[MAXN];
int head[MAXN];
int dad[MAXN];//tree
bool v[MAXN];
int yaLi[MAXN];
int depth[MAXN];//depth
int f[MAXN][16];//for doubling
int H;
int maxYaLi=0;
int root=1,newp;
map<pair<int,int>,int> zuzong;
int n,k;
void vAdd(int x,int y);
void doUnion(int x,int y);
void doInit(void);
void lca(int p);
void getMax(int p);
void bfs(int root);
void dfs(int p,int fat);
int doFind(int x);
int readLca(int p1,int p2);
int getLca(int p1,int p2);
int main(void)
{
scanf("%d%d",&n,&k);
H=1.0*log(n)/log(2);
for(int i=1;i<n;++i)
{
int x,y;
scanf("%d%d",&x,&y);
vAdd(x,y);
vAdd(y,x);
}
bfs(1);
//or dfs(1,0);
for(int i=1;i<=k;++i)
{
int x,y;
scanf("%d%d",&x,&y);
int lca=getLca(x,y);
++yaLi[x];
++yaLi[y];
--yaLi[lca];
--yaLi[f[lca][0]];
}
memset(v,0,sizeof(v));
getMax(1);
printf("%d\n",maxYaLi);
return 0;
}
void vAdd(int x,int y)
{
++newp;
e[newp].to=y;
e[newp].nex=head[x];
head[x]=newp;
}
void getMax(int p)
{
v[p]=1;
for(int i=head[p];i;i=e[i].nex)
{
int y=e[i].to;
if(v[y])continue;
else
{
getMax(y);
yaLi[p]+=yaLi[y];
}
}
maxYaLi=max(maxYaLi,yaLi[p]);
}
int getLca(int p1,int p2)
{
if(depth[p1]<depth[p2])
{
p1^=p2;
p2^=p1;
p1^=p2;
}
for(int i=H;i>=0;--i)
{
if(depth[f[p1][i]]>=depth[p2])
{
p1=f[p1][i];
}
}
if(p1==p2)return p1;
for(int i=H;i>=0;--i)
{
if(f[p1][i]!=f[p2][i])
{
p1=f[p1][i];
p2=f[p2][i];
}
}
return f[p1][0];
}
#include<queue>
void bfs(int root)
{
queue<int> q;
q.push(root);
depth[root]=1;
v[root]=1;
while(!q.empty())
{
int u=q.front();
q.pop();
for(int i=head[u];i;i=e[i].nex)
{
int y=e[i].to;
if(v[y])continue;
else
{
v[y]=1;
depth[y]=depth[u]+1;
f[y][0]=u;
for(int j=1;j<=H;++j)
{
f[y][j]=f[f[y][j-1]][j-1];
}
q.push(y);
}
}
}
}
void dfs(int p,int fat)
{
depth[p]=depth[fat]+1;
f[p][0]=fat;
for(int i=1;i<=H;++i)
{
f[p][i]=f[f[p][i-1]][i-1];
}
for(int i=head[p];i;i=e[i].nex)
{
int y=e[i].to;
if(y==fat)continue;
else dfs(y,p);
}
}
There is also a 41-point code (Tarjan)
#include<cstdio>
#include<iostream>
#include<utility>
#include<map>
#include<cstring>
using namespace std;
const int MAXN=5e4+5;
struct ed
{
int to,nex,w;
} e[MAXN];
int head[MAXN];
int fa[MAXN];//union-find
int dad[MAXN];//tree
bool v[MAXN];
int yaLi[MAXN];
int maxYaLi=0;
int root=1,newp;
map<pair<int,int>,int> zuzong;
int n,k;
void vAdd(int x,int y);
void doUnion(int x,int y);
void doInit(void);
int doFind(int x);
void lca(int p);
int readLca(int p1,int p2);
void getMax(int p);
int main(void)
{
scanf("%d%d",&n,&k);
doInit();
for(int i=1;i<n;++i)
{
int x,y;
scanf("%d%d",&x,&y);
vAdd(x,y);
vAdd(y,x);
}
lca(1);
for(int i=1;i<=k;++i)
{
int x,y;
scanf("%d%d",&x,&y);
int lca=readLca(x,y);
++yaLi[x];
++yaLi[y];
--yaLi[lca];
--yaLi[dad[lca]];
}
memset(v,0,sizeof(v));
getMax(1);
printf("%d\n",maxYaLi);
return 0;
}
void vAdd(int x,int y)
{
++newp;
e[newp].to=y;
e[newp].nex=head[x];
head[x]=newp;
}
void doInit(void)
{
for(int i=1;i<=n;++i)
{
fa[i]=i;
}
}
void doUnion(int x,int y)
{
x=doFind(x);
y=doFind(y);
fa[x]=y;
}
int doFind(int x)
{
if(fa[x]==x)return x;
else return fa[x]=doFind(fa[x]);
}
void lca(int u)
{
v[u]=1;
for(int i=head[u];i;i=e[i].nex)
{
int y=e[i].to;
if(v[y])continue;
else
{
dad[y]=u;
lca(y);
doUnion(y,u);
}
}
for(int i=1;i<=n;++i)
{
if(i==u)continue;
else
{
if(v[i])
{
zuzong[make_pair(u,i)]=doFind(i);
}
}
}
}
int readLca(int p1,int p2)
{
pair<int,int> pa=make_pair(p1,p2),pb=make_pair(p2,p1);
int z1=zuzong[pa];
if(z1)return z1;
else return zuzong[pb];
}
void getMax(int p)
{
v[p]=1;
for(int i=head[p];i;i=e[i].nex)
{
int y=e[i].to;
if(v[y])continue;
else
{
getMax(y);
yaLi[p]+=yaLi[y];
}
}
maxYaLi=max(maxYaLi,yaLi[p]);
}