小明の雜貨鋪

Segment Tree on Tree Heavy Path Decomposition 树链剖分 把一棵树分割成若干条链，以便于维护（路径、子树）信息。 重链剖分 (Heavy Path Decomposition) 从树上每个 轻节点 出发，不断向下走 重边，构成一条链。这样，树被剖分成了 lll 条链（lll 是轻节点的数量）。对于节点数为 nnn 的树，从任意节点向上走到根节点，经过的轻边数量不超过 log⁡n\log nlogn。 使用两次 DFS 完成重链剖分。 12345678910111213141516171819202122232425262728293031323334353637const int N = 1e6 + 8;std::vector<int> E[N];int fa[N], hson[N], siz[N], dep[N], top[N];int unix, dfsn[N], dfsnR[N], tdfsn[N]; // DFS 树: 时间戳 DFS 序 子树的最大 DFS 序 DFS 序对应的节点编号void...

TreeDP 树，有根有点权。点集 SSS 满足：若父节点 ∈S\in S∈S，则子节点 ∉S\not\in S∈S。最大化 SSS 点权和。（ 树的最大独立集 ） 12345678910int n, w[N], dp[N][2];void dfs(int u) { dp[u][1] = w[u]; for (auto v : E[u]) { dfs(v); dp[u][0] += max(dp[v][0], dp[v][1]); dp[u][1] += dp[v][0]; }}print(max(dp[rt][0], dp[rt][1])); 树，有根有点权。mmm 元点集 SSS 满足：若子节点 ∈S\in S∈S，则父节点 ∈S\in S∈S。最大化 SSS 点权和。（ 树上背包 ） 123456789101112int n, m, w[N], dp[N][M];void dfs(int u) { dp[u][1] = w[u]; ...

指针 一、指针的基本概念 变量的地址 获取 变量在内存中的 起始地址，使用 & 变量名。 123int a;cout << (void*)&a << '\n'; // 十六进制cout << (long long)&a << '\n'; // 十进制 指针变量 简称 指针 ， 存放 变量在内存中的起始地址，使用 数据类型 * 变量名 ， 数据类型 * 也是一种数据类型，即 x 型指针。 对指针赋值 使用 指针 = & 地址，称为指向某变量，被指向的类型称为基类型。 12345int a;int* pa = &a;cout << (long long)&a << '\n';cout << (long long)pa << '\n';// 以上两行的输出结果相同 二、使用指针 注意：声明指针变量后必须初始化。 * 运算符（即...

本笔记基于中国大学慕课《C/C++ 语言程序设计(下)（沈萦华老师）》及「OpenJudge - 信通学院编程小组」。 [[#§0 C++ 基础 |§0 C++ 基础]] [[#§0.1 指针 |§0.1 指针]] [[#§0.2 命名空间 |§0.2 命名空间]] [[#§0.3 引用 |§0.3 引用]] [[#§0.4 函数 |§0.4 函数]] [[#§1 类和对象基本概念与特性 |§1 类和对象基本概念与特性]] [[#§1.1 类的基本概念 |§1.1 类的基本概念]] [[#§1.2 构造函数与析构函数 |§1.2 构造函数与析构函数]] [[#§1.3 this 指针 |§1.3 this 指针]] [[#§2 类的进阶特性 |§2 类的进阶特性]] [[#§2.1 静态成员 static|§2.1 静态成员 static]] [[#§2.2 常量成员函数 const|§2.2 常量成员函数 const]] [[#§2.3 友元 friend|§2.3 友元 friend]] [[#§2.4 ...

The 2022 ICPC Asia Shenyang Regional Contest (The 1st Universal Cup, Stage 1: Shenyang)