Znzryb's Blog
0%

P3128 [USACO15DEC] Max Flow P（打印）

Posted on Edited on

思路讲解

用的tarjan方法求的LCA（倍增我不太会）

参考讲解（树上差分）

image

AC代码

AC
https://www.luogu.com.cn/record/199856000

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
const ll MAXN=static_cast<ll>(5e5)+10;
ll N,K;
vector<ll> g[MAXN];
ll fa[MAXN],par[MAXN];
bool vis[MAXN],done[MAXN],vis2[MAXN];
vector<pll> route[MAXN];
ll diff[MAXN];	// 树上差分数组
ll ans[MAXN];	// 原数组
// https://www.luogu.com.cn/problem/P3128
// LCA+树上差分
ll find(int x) {
	if(fa[x]==x) return fa[x];
	fa[x]=find(fa[x]);
	return fa[x];
}
void dfs(int x,int pa) {  // 求LCA以及进行树上差分
	vis[x]=true;fa[x]=x;	// 一开始并查集要指向自己
	par[x]=pa;	// 另外的一个专门记录父节点的数组
	for(int i=0;i<g[x].size();++i) {
		if(vis[g[x][i]]) continue;	// 走过的我们不走了
		dfs(g[x][i],x);
		fa[g[x][i]]=x;	// 并查集指向自己父亲
	}
	for(int i=0;i<route[x].size();++i) {
		ll t=route[x][i].first,idx=route[x][i].second;
		if(vis[t] && !done[idx]) {	// 树上差分操作
			done[idx]=true;	// 避免重复树上差分
			diff[find(t)]-=1;	// 这里-1是因为最近公共祖先会被记两次
			diff[x]+=1;
			diff[t]+=1;			// 在区间开头+1
			diff[par[find(t)]]-=1; // 在区间结束-1
		}
	}
}
// 还原差分数组为原数组
void restorDiff(int x) {
	vis2[x]=true;
	for(int i=0;i<g[x].size();++i) {
		if(vis2[g[x][i]]) continue;	// 走过的我们不走了
		restorDiff(g[x][i]);
		ans[x]+=ans[g[x][i]];
	}
	ans[x]+=diff[x];
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>N>>K;
	for(int i=1;i<=N-1;++i) {
		ll u,v;
		cin>>u>>v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	for(int i=1;i<=K;++i) {
		ll s,t;
		cin>>s>>t;
		route[s].push_back({t,i});
		route[t].push_back({s,i});
	}
	// 应当认为1的根节点是0或者是无，而不是自己
	dfs(1,0);
	restorDiff(1);
	ll Ans=0;
	for(int i=1;i<=N;++i) {
		Ans=max(Ans,ans[i]);
	}
	cout<<Ans<<endl;
	// for(int i=1;i<=N;++i) {	// debug
	// 	cout<<ans[i]<<' ';
	// }
	// cout<<endl;
	return 0;
}
/*
AC
https://www.luogu.com.cn/record/199856000
*/

心路历程（WA，TLE，MLE……）

这道题数据范围好像是有点问题，需要开到5e5+10才行，反正有点离谱，也不知道是我0数错了还是什么，反正有点离谱