D. Misha, Grisha and Underground

这个题目算一个树链剖分的裸题,但是这个时间复杂度注意优化。

这个题目可以选择树剖+线段树,时间复杂度有点高,比较这个本身就有n*logn*logn

但是就是lca+一点点思维就完全不卡时间。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <vector>
#include <stack>
#include <map>
#include <string>
#define inf 0x3f3f3f3f
#define inf64 0x3f3f3f3f3f3f3f3f
using namespace std;
const int maxn = 2e5 + 10; int f[maxn];//f 保存u的父亲节点
int dep[maxn];//dep保存节点u 的深度
int siz[maxn];//siz保存以u为根的子节点的个数
int son[maxn];//son 保存u的重儿子
int rk[maxn];//rk当前dfs序在树中所对应的节点
int top[maxn];// top保存当前结点所在链的顶端结点
int id[maxn];//dfs的执行顺序 int a[maxn];
int n;
int sum[maxn * 4], lazy[maxn * 4];
//------------------线段树部分---------------//
void push_up(int id) {
sum[id] = (sum[id << 1] + sum[id << 1 | 1]);
} void build(int id, int l, int r) {
lazy[id] = -1;
sum[id] = 0;
if (l == r) return;
int mid = (l + r) >> 1;
build(id << 1, l, mid);
build(id << 1 | 1, mid + 1, r);
push_up(id);
} void push_down(int id, int len1, int len2) {
if (lazy[id] == -1) return;
lazy[id << 1] = lazy[id << 1 | 1] = lazy[id];
sum[id << 1] = len1 * lazy[id];
sum[id << 1 | 1] = len2 * lazy[id];
lazy[id] = -1;
} void update(int id, int l, int r, int x, int y, int val) {
// printf("id=%d l=%d r=%d x=%d y=%d val=%d\n", id, l, r, x, y, val);
if (x <= l && y >= r) {
sum[id] = (r - l + 1)*val;
lazy[id] = val;
return;
}
int mid = (l + r) >> 1;
push_down(id, mid - l + 1, r - mid);
if (x <= mid) update(id << 1, l, mid, x, y, val);
if (y > mid) update(id << 1 | 1, mid + 1, r, x, y, val);
push_up(id);
} int query(int id, int l, int r, int x, int y) {
if (x <= l && y >= r) return sum[id];
int mid = (l + r) >> 1, ans = 0;
push_down(id, mid - l + 1, r - mid);
if (x <= mid) ans = (ans + query(id << 1, l, mid, x, y));
if (y > mid) ans = (ans + query(id << 1 | 1, mid + 1, r, x, y));
return ans;
} //------------------------树链剖分-------------------//
// int f[maxn];//f 保存u的父亲节点
// int dep[maxn];//dep保存节点u 的深度
// int siz[maxn];//siz保存以u为根的子节点的个数
// int son[maxn];//son 保存u的重儿子
// int rk[maxn];//rk当前dfs序在树中所对应的节点
// int top[maxn];// top保存当前结点所在链的顶端结点
// int id[maxn];//dfs的执行顺序
struct node {
int v, nxt;
node(int v = 0, int nxt = 0) :v(v), nxt(nxt) {}
}ex[maxn];
int head[maxn], cnt = 0, tot;
void init() {
cnt = 0, tot = 0;
memset(son, 0, sizeof(son));
memset(head, -1, sizeof(head));
}
void add(int u, int v) {
ex[cnt] = node(v, head[u]);
head[u] = cnt++;
ex[cnt] = node(u, head[v]);
head[v] = cnt++;
} void dfs1(int u, int fa, int depth) {
f[u] = fa; dep[u] = depth; siz[u] = 1;
for (int i = head[u]; i != -1; i = ex[i].nxt) {
int v = ex[i].v;
if (v == fa) continue;
dfs1(v, u, depth + 1);
siz[u] += siz[v];
if (siz[v] > siz[son[u]]) son[u] = v;
}
} void dfs2(int u, int t) {
top[u] = t;
id[u] = ++tot;//标记dfs序
rk[tot] = u;//序号tot对应的结点u
if (!son[u]) return;
dfs2(son[u], t);
/*我们选择优先进入重儿子来保证一条重链上各个节点dfs序连续,
一个点和它的重儿子处于同一条重链,所以重儿子所在重链的顶端还是t*/
for (int i = head[u]; i != -1; i = ex[i].nxt) {
int v = ex[i].v;
if (v != son[u] && v != f[u]) dfs2(v, v);//一个点位于轻链底端,那么它的top必然是它本身
}
} void update2(int x, int y, int z)//修改x到y路径的值
{
// printf("x=%d y=%d %d %d\n", x, y, top[x], top[y]);
while (top[x] != top[y])//不在同一条链上
{
// printf("%d %d\n", id[top[x]], id[x]);
if (dep[top[x]] < dep[top[y]]) swap(x, y);//x为深度大的链
update(1, 1, n, id[top[x]], id[x], z);//x为深度大的链
x = f[top[x]];//深度大的向上跳
}
if (dep[x] > dep[y]) swap(x, y); //这里x和y在同一条链
// printf("id[%d]=%d id[%d]=%d\n", x, id[x], y, id[y]);
update(1, 1, n, id[x], id[y], z); //x和y这条链的更新
} int query2(int x, int y) {
int ret = 0;
while (top[x] != top[y]) {
if (dep[top[x]] < dep[top[y]]) swap(x, y);
ret = (ret + query(1, 1, n, id[top[x]], id[x]));
x = f[top[x]];
}
if (dep[x] > dep[y]) swap(x, y);
ret = (ret + query(1, 1, n, id[x], id[y]));
return ret;
} //------------------树链剖分结束-------------------// int main() {
init();
int m, x;
scanf("%d%d", &n, &m);
for (int i = 2; i <= n; i++) scanf("%d", &x), add(x, i);
dfs1(1, -1, 1), dfs2(1, 1);
build(1, 1, n);
// for (int i = 1; i <= n; i++) printf("id[%d]=%d\n", i, id[i]);
while (m--) {
int l, r, c, ans = 0;
scanf("%d%d%d", &l, &r, &c);
// printf("l=%d r=%d c=%d\n", l, r, c);
update2(r, l, 1);
ans = max(ans, query2(c, l));
ans = max(ans, query2(c, r));
update(1, 1, n, 1, n, 0); update2(c, l, 1);
ans = max(ans, query2(r, l));
ans = max(ans, query2(r, c));
update(1, 1, n, 1, n, 0); update2(r, c, 1);
ans = max(ans, query2(l, c));
ans = max(ans, query2(l, r));
update(1, 1, n, 1, n, 0); printf("%d\n", ans);
}
return 0;
}

  

最新文章

  1. Linux中profile、bashrc、bash_profile之间的区别和联系
  2. 各种模板(part 1)
  3. Frogger
  4. C语言中char* 和 char []区别
  5. 一台Ubuntu server上安装多实例MySQL
  6. 【HDOJ】1073 Online Judge
  7. 【模拟】Codeforces 710A King Moves
  8. thinkphp整合系列之短信验证码、订单通知
  9. js任意数组按下标相加
  10. angularjs 中通过 $location 进行路由跳转传参
  11. 爬取w3c课程—Urllib库使用
  12. 如何利用 jQuery 修改 css 中带有 !important 的样式属性?
  13. OpFlex
  14. CS231n学习笔记-图像分类笔记(上篇)
  15. Thinkphp --- 路由定义
  16. 170608、Spring 事物机制总结
  17. IOS [转]setValue和setObject的区别
  18. 如何在CentOS 7上使用vsftpd(FTP)的配置文件介绍
  19. 开源爬虫Labin,Nutch,Neritrix介绍和对比
  20. Java Web开发后端常用技术汇总

热门文章

  1. Spring+Hibernate整合配置 --- 比较完整的spring、hibernate 配置
  2. Codeup 25594 Problem H 例题5-8 Fibonacci数列
  3. JuiceSSH:安卓平台免费好用的 SSH 客户端
  4. Daily Scrum 1/5/2015
  5. stand up meeting 12-2
  6. mysql datetime类型 按格式在页面输出
  7. 你自学半年也搞不懂的go底层,看这篇。这篇讲 go的数组、切片、Maps
  8. Spring Boot 中使用自定义注解,AOP 切面打印出入参日志及Dubbo链路追踪透传traceId
  9. [Abp vNext 入坑分享] - 3.简单的用户模块功能开发
  10. 在dwr的调用类里获取请求信息