题目大意:
  给你一棵n个点的树,有m次操作,每次将给定的路径上所有点的点权+1。
  问最后最大的点权是多少。

思路:
  

 #include<cstdio>
#include<cctype>
#include<vector>
inline int getint() {
register char ch;
while(!isdigit(ch=getchar()));
register int x=ch^'';
while(isdigit(ch=getchar())) x=(((x<<)+x)<<)+(ch^'');
return x;
}
const int N=;
std::vector<int> e[N];
inline void add_edge(const int &u,const int &v) {
e[u].push_back(v);
e[v].push_back(u);
}
class SegmentTree {
#define _left <<1
#define _right <<1|1
private:
int max[N<<],tag[N<<];
void push_down(const int &p) {
max[p _left]+=tag[p];
max[p _right]+=tag[p];
tag[p _left]+=tag[p];
tag[p _right]+=tag[p];
tag[p]=;
}
void push_up(const int &p) {
max[p]=std::max(max[p _left],max[p _right]);
}
public:
void modify(const int &p,const int &b,const int &e,const int &l,const int &r) {
if(b==l&&e==r) {
max[p]++;
tag[p]++;
return;
}
push_down(p);
const int mid=(b+e)>>;
if(l<=mid) modify(p _left,b,mid,l,std::min(mid,r));
if(r>mid) modify(p _right,mid+,e,std::max(mid+,l),r);
push_up(p);
}
int query() const {
return max[];
}
#undef _left
#undef _right
};
SegmentTree t;
int n,par[N],dep[N],top[N],low[N],size[N],son[N],id[N];
void dfs1(const int &x,const int &par) {
::par[x]=par;
dep[x]=dep[par]+;
size[x]=;
for(unsigned i=;i<e[x].size();i++) {
const int &y=e[x][i];
if(y==par) continue;
dfs1(y,x);
size[x]+=size[y];
if(size[y]>size[son[x]]) son[x]=y;
}
}
void dfs2(const int &x) {
id[x]=++id[];
if(x==son[par[x]]) {
top[x]=top[par[x]];
} else {
top[x]=x;
}
if(son[x]) dfs2(son[x]);
for(unsigned i=;i<e[x].size();i++) {
const int &y=e[x][i];
if(y==par[x]||y==son[x]) continue;
dfs2(y);
}
}
inline void modify(int u,int v) {
while(top[u]!=top[v]) {
if(dep[top[u]]<dep[top[v]]) std::swap(u,v);
t.modify(,,n,id[top[u]],id[u]);
u=par[top[u]];
}
if(dep[u]<dep[v]) std::swap(u,v);
t.modify(,,n,id[v],id[u]);
}
int main() {
n=getint();
const int m=getint();
for(register int i=;i<n;i++) {
add_edge(getint(),getint());
}
dfs1(,);
dfs2();
for(register int i=;i<m;i++) {
const int s=getint(),t=getint();
modify(s,t);
}
printf("%d\n",t.query());
return ;
}

树链剖分模板题。

最新文章

  1. js作用域问题
  2. iOS 关于字体根据不同屏幕尺寸等比适配的问题(zz)
  3. MineCraft note
  4. 转载 Servlet3.0中使用注解配置Servle
  5. 【转】DCC32的参数详解
  6. SQL0294N 容器已在使用中。 SQLSTATE=42730
  7. java 布尔值一种赋值方法
  8. 安装bower
  9. json中文乱码问题
  10. JAVA流式布局管理器--JAVA基础
  11. CXF-01: WebService的第一个例子
  12. 个人总结ASP.NET必备面试题
  13. 报错:keep must be either &quot;first&quot;, &quot;last&quot; or False
  14. .Net RPC框架Thrift的用法
  15. 基于Hadoop2.6.5(HA)的Hive1.2.1的MySQL方式配置
  16. 三、K3 WISE 开发插件《K3 WISE开发手册》
  17. [译]新的CCSDS图像压缩推荐标准
  18. linux -- Ubuntu network-manager
  19. OpenSSL学习笔记
  20. Cocos2dx之touch事件

热门文章

  1. Educational Codeforces Round 56 (Rated for Div. 2) ABCD
  2. hdu 3473 (划分树)2
  3. Django随笔 01
  4. (转)如何用python抓取网页并提取数据
  5. canvas知识02:图片放大镜效果
  6. 51Nod-1586-约数和
  7. 最大流算法 ISAP 模板 和 Dinic模板
  8. 51nod 扔盘子
  9. 【洛谷 P4777】 【模板】扩展中国剩余定理(EXCRT)
  10. 通过监测DLL调用探测Mimikatz