[USACO15DEC] 最大流Max Flow && Tarjan 线性 LCA 教学？

痛定思痛。 2021-11-04 09:38 129阅读 0赞

[题面][Link 1]

显然是树上差分模板题啦，不知道树上差分的童鞋可以去百度一下，很简单。

然后顺带学了一下 tarjan 的 O(N+Q) 离线求LCA的算法 (准确的说难道不应该带个并查集的复杂度吗？？？)

算法过程具体可以看[这里][Link 2]

这里说一下我的理解。

大概可以把所有点分成三类(对于每个dfs的状态)：已经遍历到的并且不在dfs栈中的点，已经遍历到并且在dfs栈中的点，未被遍历到的点。

其中，第二种的所有点构成了当前的右链。

然后dfs的过程就是，每个节点的子树遍历完了之后，它自己也就变成了第一种点，我们把这颗子树并到这个节点爸爸上。注意，此时它的爸爸必然是第二种节点。

稍加推理我们就可以发现，任意时刻每个前两种节点所在的并查集的根必然是它最近的一个第二种节点的祖先(如果是第二种节点就是它自己)。

然后我们每次dfs刚刚进入一个节点x的时候，就先回答涉及它的LCA询问：

1.若另一个点y已经被dfs过了(也即是前两种节点)，那么它们的LCA就是 get\_root(y)。这并不难理解，因为x在右链上，所以y与x的LCA必然是右链上离y最近的点，也就是get\_root(y)。

2.若另一个点y没有被dfs过，那么不用管，因为我们必然会在dfs到y的时候处理x。

这么做之后，每组LCA只会被找一次。

复杂度还是线性的，代码还贼好写w

#include<bits/stdc++.h>
    #define ll long long
    using namespace std;
    #define pb push_back
    const int N=50005;
    
    inline int read(){
    	int x=0; char ch=getchar();
    	for(;!isdigit(ch);ch=getchar());
    	for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';
    	return x;
    }
    
    vector<int> g[N],ask[N];
    int n,m,f[N],a[N],p[N],ans;
    
    int gr(int x){ return p[x]==x?x:(p[x]=gr(p[x]));}
    
    void dfs(int x,int fa){
    	f[x]=fa;
    	for(int i:ask[x]) if(f[i]>=0) a[gr(i)]--,a[f[gr(i)]]--;
    	for(int i:g[x]) if(i!=fa) dfs(i,x),p[i]=x;
    }
    
    void update(int x){
    	for(int i:g[x]) if(i!=f[x]) update(i),a[x]+=a[i];
    	ans=max(ans,a[x]);
    }
    
    inline void solve(){
    	for(int U,V;m;m--)
    	    U=read(),V=read(),a[U]++,a[V]++,ask[U].pb(V),ask[V].pb(U);
    	memset(f,-1,sizeof(f)),dfs(1,0),update(1);
    }
    
    int main(){
    	n=read(),m=read();
    	for(int i=1;i<=n;i++) p[i]=i;
    	for(int i=1,U,V;i<n;i++) U=read(),V=read(),g[U].pb(V),g[V].pb(U);
    	solve(),printf("%d\n",ans);
    	return 0;
    }

转载于:https://www.cnblogs.com/JYYHH/p/11312133.html

[Link 1]: https://www.luogu.org/problem/P3128
[Link 2]: https://www.cnblogs.com/JVxie/p/4854719.html