题解——洛谷P3128 [USACO15DEC]最大流Max Flow
2024-10-21 12:36:12
裸的树上差分
因为要求点权所以在点上差分即可
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int MAXN = ;
const int MAXM = ;
const int MAXlog = ;
int cnt=,u[MAXN*],v[MAXN*],first[MAXN],next[MAXN*];
int cf[MAXN];
int dep[MAXN],jump[MAXN][MAXlog+];
int n,k;
void addedge(int ux,int vx){
cnt++;
u[cnt]=ux;
v[cnt]=vx;
next[cnt]=first[ux];
first[ux]=cnt;
}
void dfs(int u,int f){
dep[u]=dep[f]+;
jump[u][]=f;
for(int i=;i<=MAXlog;i++)
jump[u][i]=jump[jump[u][i-]][i-];
for(int i=first[u];i;i=next[i])
if(v[i]!=f)
dfs(v[i],u);
}
int lca(int x,int y){
if(dep[x]<dep[y])
swap(x,y);
for(int i=MAXlog;i>=;i--)
if(dep[x]-(<<i)>=dep[y])
x=jump[x][i];
if(x==y)
return x;
for(int i=MAXlog;i>=;i--)
if(jump[x][i]!=jump[y][i]){
x=jump[x][i];
y=jump[y][i];
}
return jump[x][];
}
int ans=;
void dfs2(int u,int f){
for(int i=first[u];i;i=next[i]){
if(v[i]==f)
continue;
dfs2(v[i],u);
cf[u]+=cf[v[i]];
}
if(cf[u]>ans)
ans=cf[u];
}
int main(){
scanf("%d %d",&n,&k);
for(int i=;i<=n-;i++){
int a,b;
scanf("%d %d",&a,&b);
addedge(a,b);
addedge(b,a);
}
dfs(,);
for(int i=;i<=k;i++){
int a,b;
scanf("%d %d",&a,&b);
cf[a]++;
cf[b]++;
int l=lca(a,b);
cf[l]-=;
cf[jump[l][]]-=;
}
dfs2(,);
printf("%d",ans);
return ;
}
最新文章
- 学习RBAC 用户&#183;角色&#183;权限&#183;表
- linux top命令查看内存及多核CPU的使用讲述
- rtc 关机闹钟1 app层
- 年月日 生日 js插件
- Python 元组知识点
- java中实现链表(转)
- python几大排序算法
- CSS之切出横幅
- codeforces GYM 100114 J. Computer Network 无相图缩点+树的直径
- 第二章——Serializable的使用(跨进程使用和Intent的传递对象)
- linux之iptable
- Chrome 开发者工具断点调试(视频教程)
- cordova 插件开发
- 实例讲解webpack的基本使用第二篇
- C语言第七次博客作业--一二维数组
- 2014-10-30NOIP复习题1
- keepalived+nginx负载均衡+ApacheWeb实现高可用
- H5 video标签的属性
- BZOJ3945 : 无聊的邮递员
- 关于set_input_delay的用法分析