求助lca+树上差分。悬2关。
查看原帖
求助lca+树上差分。悬2关。
590609
jiangjiangQwQ楼主2023/8/4 21:24
#include<bits/stdc++.h>
#include<algorithm>
using namespace std;
#define dy; ios::sync_with_stdio(false),cin.tie(),cout.tie();
#define int long long
#define re register
#define For(i,l,r) for(re int i=l;i<=r;i++)
#define Rep(i,l,r) for(re int i=l;i>=r;i--)
const int N=3e5+5;
inline void read(int &x) {
	x=0;
	int f=1;
	char c=getchar();
	while(!isdigit(c)) {
		if(c=='-') f=-1;
		c=getchar();
	}
	while(isdigit(c)) {
		x=x*10+c-'0';
		c=getchar();
	}
	x*=f;
}
inline void write(int x) {
	if(x<0) {
		x=-x;
		putchar('-');
	}
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
int dep[N],f[N][20],n,m,x,y,sum[N],ans;
vector<int> edge[N];
inline void deal_first(int u,int fa) {
	dep[u]=dep[fa]+1;
	for(int i=0; i<=19; i++) f[u][i+1]=f[f[u][i]][i];
	for(int j=0; j<edge[u].size(); j++) {
		int v=edge[u][j];
		if(v==fa) continue;
		f[v][0]=u;
		deal_first(v,u);
	}
}
int LCA(int x,int y) {
	if(dep[x]<dep[y]) swap(x,y);
	for(int i=20; i>=0; i--) {
		if(dep[f[x][i]]>=dep[y]) x=f[x][i];
		if(x==y) return x;
	}
	for(int i=20; i>=0; i--) {
		if(f[x][i]!=f[y][i]) {
			x=f[x][i];
			y=f[y][i];
		}
	}
	return f[x][0];
}
inline void add(int x,int y) {
	int lca=LCA(x,y);
	++sum[x];
	++sum[y];
	--sum[lca];
	--sum[f[lca][0]];
}
inline void query(int u,int fa) {
	for(int j=0; j<edge[u].size(); j++) {
		int v=edge[u][j];
		if (v==fa) continue;
		query(v,u);
		sum[u]+=sum[v];
	}
	ans=max(ans,sum[u]);
}
signed main() {
	read(n);
	read(m);
	For(i,1,n-1) {
		read(x);
		read(y);
		edge[x].push_back(y);
		edge[y].push_back(x);
	}
	deal_first(1,0);
	For(i,1,m) {
		read(x);
		read(y);
		add(x,y);
	}
//	For(i,1,n) cout<<sum[i]<<endl;
	query(1,0);
	cout<<ans;
	return 0;
}
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
Output:
8

程序输出 1818。调不出。

2023/8/4 21:24
加载中...