裸的树上差分

因为要求点权所以在点上差分即可

#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 ;
}

最新文章

  1. 学习RBAC 用户&#183;角色&#183;权限&#183;表
  2. linux top命令查看内存及多核CPU的使用讲述
  3. rtc 关机闹钟1 app层
  4. 年月日 生日 js插件
  5. Python 元组知识点
  6. java中实现链表(转)
  7. python几大排序算法
  8. CSS之切出横幅
  9. codeforces GYM 100114 J. Computer Network 无相图缩点+树的直径
  10. 第二章——Serializable的使用(跨进程使用和Intent的传递对象)
  11. linux之iptable
  12. Chrome 开发者工具断点调试(视频教程)
  13. cordova 插件开发
  14. 实例讲解webpack的基本使用第二篇
  15. C语言第七次博客作业--一二维数组
  16. 2014-10-30NOIP复习题1
  17. keepalived+nginx负载均衡+ApacheWeb实现高可用
  18. H5 video标签的属性
  19. BZOJ3945 : 无聊的邮递员
  20. 关于set_input_delay的用法分析

热门文章

  1. html5-css渐变应用小实例,按钮
  2. poj1741 树上的分治
  3. codeforces 980D Perfect Groups
  4. Spark学习之路 (十一)SparkCore的调优之Spark内存模型
  5. FTL 数字有逗号
  6. 任务调度工具 Apache Airflow 初识
  7. flask 处理表单数据
  8. 禁用HTTP.sys,导致80端口被禁用和IIS服务无法启动解决办法
  9. mac电脑复制粘贴使用command+c command+v
  10. Numpy 基本除法运算和模运算