社区讨论
求助大佬!!
P3128[USACO15DEC] Max Flow P参与者 1已保存回复 0
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @mi863c3p
- 此快照首次捕获于
- 2025/11/21 09:14 4 个月前
- 此快照最后确认于
- 2025/11/21 09:14 4 个月前
CPP
#include<iostream>
#include<cstdio>
#define MA 50005
using namespace std;
int n,k;
int fis[MA<<2],nex[MA<<2],go[MA<<2],tot;
int p[MA];
int f[MA][25],dep[MA];
int ans=0;
inline int read(){
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();};
while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();};
return x*f;
}
inline void add(int u,int v){
nex[++tot]=fis[u];
fis[u]=tot;
go[tot]=v;
return ;
}
inline void deal(int u,int fat){
int i;
dep[u]=dep[fat]+1;
for(i=1;f[u][i];i++){
f[u][i]=f[f[u][i-1]][i-1];
}
for(int e=fis[u];e;e=nex[e]){
int v=go[e];
if(v==fat){
continue;
}
f[v][0]=u;
deal(v,u);
}
return ;
}
inline int lca(int x,int y){
int i;
if(dep[x]<dep[y]){
swap(x,y);
}
for(i=20;i>=0;i--){
if(dep[x]-(1<<i)>=dep[y]){
x=f[x][i];
}
if(x==y){
return x;
}
}
for(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 dfs(int u,int fat){
for(int e=fis[u];e;e=nex[e]){
int v=go[e];
if(v==fat){
continue;
}
dfs(v,u);
p[u]+=p[v];
}
ans=max(ans,p[u]);
return ;
}
int main(){
int i;
int x,y;
n=read();k=read();
for(i=1;i<n;i++){
x=read();y=read();
add(x,y);
add(y,x);
}
deal(1,0);
for(i=1;i<=k;i++){
x=read();y=read();
++p[x];++p[y];--p[lca(x,y)];--p[f[lca(x,y)][0]];
}
dfs(1,0);
printf("%d",ans);
return 0;
}
回复
共 0 条回复,欢迎继续交流。
正在加载回复...