目录
- 0x00 LCA的六种求法
- 0x10 Kruskal重构树
- 0x20 虚树
- 0x30 点分治
- 0x31 静态点分治
- 0x32 动态点分治
- 0x33 性质与总结
- 0x34 例题
- 0x341 P3806 【模板】点分治1
- 0x342 P6329 【模板】点分树 | 震波
- 0x343 P4149 [IOI2011] Race
- 0x344 P2634 [国家集训队] 聪聪可可
- 0x345 P4178 Tree
- 0x347 P4075 [SDOI2016] 模式字符串
- 0x348 CF914E Palindromes in a Tree
- 0x349 P3345 [ZJOI2015] 幻想乡战略游戏【咕咕咕】
- 0x34A AT_cf17_final_j Tree MST【咕咕咕】
- 0x34B P6199 [EER1] 河童重工【咕咕咕】
- 0x34C CF150E Freezing with Style【咕咕咕】
- 0x40 长链剖分
- 0x50 树上启发式合并
- 0x60 笛卡尔树：单调栈进阶
原文链接
0x00 LCA的六种求法
0x01 倍增法
预处理复杂度为\(\Theta(n\log n)\)，单词查询复杂度为\(\Theta(\log n)\)，空间复杂度为\(\Theta(n\log n)\)。
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std ;
const int MAXN = 500010 ;
int n ,m ,s ;
struct Edge{
int to ,next ;
}edge[MAXN<<1] ;
int head[MAXN] ,edge_cnt ;
inline void edge_add(int from , int to){
edge[++edge_cnt].to = to ;
edge[edge_cnt].next = head[from] ;
head[from] = edge_cnt ;
}
int dep[MAXN] ,st[MAXN][35] ;
inline void dfs(int node , int fa){
dep[node] = dep[fa] + 1 ;
for(int i = 1;i <= 30;++i) st[node][i] = st[st[node][i-1]][i-1] ;
for(int i = head[node];i;i = edge[i].next){
int v = edge[i].to ;
if(v == fa)continue ;
st[v][0]=node ;
dfs(v , node) ;
}
}
inline int LCA(int x , int y){
if(dep[y] > dep[x]) swap(x , y) ;
for(int i = 30;i >= 0;--i) if(dep[st[x][i]] >= dep[y]) x = st[x][i] ;
if(x == y) return x ;
for(int i = 30;i >= 0;--i) if(st[x][i] != st[y][i]) x=st[x][i] ,y = st[y][i] ;
return st[x][0] ;
}
int main(){
ios::sync_with_stdio(0) ;cin.tie(0) ;cout.tie(0) ;
cin >> n >> m >> s ;
for(int i = 1;i < n;++i){int u ,v ;cin >> u >> v ;edge_add(u , v) ;edge_add(v , u) ;}
dfs(s,0) ;
for(int i = 1;i <= m;++i){
int a ,b ;cin >> a >> b ;
cout << LCA(a,b) << '\n' ;
}
return 0 ;
}
0x02 欧拉序
\(\Theta(n\log n)-\Theta(1)\)，空间\(\Theta(n\log n)\)，有两倍的常数。
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std ;
const int MAXN = 500010 ;
int n ,m ,s ;
struct Edge{
int to ,next ;
}edge[MAXN<<1] ;
int head[MAXN] ,edge_cnt ;
int minn[30][MAXN<<1] ,lg[MAXN<<1] ;//log空间要开到2倍
inline void edge_add(int from , int to){
edge[++edge_cnt].to = to ;
edge[edge_cnt].next = head[from] ;
head[from] = edge_cnt ;
}
int dep[MAXN] ,dfn[MAXN] ,idx ;
inline int get(int x , int y){ return dep[x] < dep[y] ? x : y ;}
inline void dfs(int node , int fa){
dep[node] = dep[fa] + 1 ;
dfn[node] = ++idx ;
minn[0][dfn[node]] = node ;//块长为1，表示自己
for(int i = head[node];i;i = edge[i].next){
int v = edge[i].to ;if(v == fa) continue ;
dfs(v , node) ;
minn[0][++idx] = node ;//递归结束后还需要再次标记
}
}
inline int LCA(int x , int y){
int u = dfn[x] ,v = dfn[y] ;
if(u > v) swap(u,v) ;
int d = lg[v - u + 1] ;//间隔的长度的log2
cout << u << ' ' << v << ' ' << d << ": " << u << ' ' << u+(1<<d)-1 << ' ' << v-(1<<d)+1 << ' ' << (v-(1<<d)+1)+(1<<d)-1 << endl ;
return get(minn[d][u] , minn[d][v-(1<<d)+1]) ;//如果位于同一个块内，则等价；否则就是两段块拼起来
}
int main(){
ios::sync_with_stdio(0) ;cin.tie(0) ;cout.tie(0) ;
cin >> n >> m >> s ;
for(int i = 1;i < n;++i){int u ,v ;cin >> u >> v ;edge_add(u , v) ;edge_add(v , u) ;}
dfs(s,0) ;
for(int i = 1;i <= n;++i) cout << dfn[i] << ' ' ;
cout << endl ;
for(int i = 2;i <= idx;++i) lg[i] = lg[i>>1] + 1 ;
for(int i = 1;i <= lg[idx];++i)
for(int j = 1;j + (1<<i) - 1 <= idx;++j) minn[i][j] = get(minn[i-1][j],minn[i-1][j+(1<<i-1)]) ;//合并两个块，求最大值
for(int i = 1;i <= m;++i){
int a ,b ;cin >> a >> b ;
cout << LCA(a,b) << '\n' ;
}
return 0 ;
}
0x03 DFS序
时间和空间复杂度和欧拉序相同，但是常数小了一半。
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
constexpr int K = 30;
constexpr int N = 5e5 + 5;
ll f[N];
vector<pii> e[N];
int n, m, lg[N];
int dn, dfn[N], dep[N], mi[K][N];
int get(int x, int y) {return dep[x] < dep[y] ? x : y;}
void dfs(int id, int ff) {
dfn[id] = ++dn;
dep[id] = dep[ff] + 1;
mi[0][dfn[id]] = ff;
for(pii _ : e[id]) {
int it = _.first;
if(it == ff) continue;
dfs(it, id);
}
}
int LCA(int u, int v) {
if(u == v) return u;
if((u = dfn[u]) > (v = dfn[v])) swap(u, v);
int d = lg[v - u++];
return get(mi[d][u], mi[d][v - (1 << d) + 1]);
}
int s ;
int main() {
ios::sync_with_stdio(0);
cin >> n >> m >> s;
for(int i = 2; i <= n; i++) lg[i] = lg[i >> 1] + 1;
for(int i = 1; i < n; i++) {
int u, v, w;
cin >> u >> v;
e[u].push_back({v, 0});
e[v].push_back({u, 0});
}
dfs(s, 0);
for(int i = 1; i <= lg[n]; i++)
for(int j = 1; j <= n; j++) {
if(j + (1 << i) - 1 <= n) mi[i][j] = get(mi[i - 1][j], mi[i - 1][j + (1 <<(i - 1))]);
}
for(int _ = 1; _ <= m; _++) {int a ,b ;
cin >> a >> b ;cout << LCA(a , b) << '\n' ;
}
return 0;
}
0x04 树剖
太慢了。
0x05 Tarjan
太慢了，还要离线。
0x06 四毛子定理
0x10 Kruskal重构树
0x11 算法简介
0x12 性质与应用
性质：
- 二叉树。
由于建树的方式是对于最小生成树上的每一条树边进行操作，所以只会有两个儿子节点。、 - 由于对于一个点多次连边的时候就会和权值节点（新节点）连边，所以所有叶子节点都是老节点。
- 由于之前
sort过，先连边的一定点权最小，又因为先连的点在下面，所以得证。
根据第三个性质可以得到重构树的核心：
因此我们可以总结出一个常用套路：当题目限制只经过权值不大于某个值的点或边的时候，我们就要考虑kruskal重构树。
0x13 点权多叉重构树
考虑拓展到点权。
- 将点权转化为边权。如果经过一条边，说明两边的点都符合条件，因此可以设这条边的边权为\(w_{u,v}=\max{a_u,a_v}\)。可以拓展到最小值（\(\max\rightarrow\min\)）。
- 边权为\(\max(w_i,w_j)\)，避免建立虚点。
0x14 例题
0x141 P4768 [NOI2018] 归程
模板题。
0x142 P4899 [IOI2018] werewolf 狼人
0x143 [模拟赛]超级加倍
转化类问题，
0x144 CF1628E Groceries in Meteor Town
感觉问题关键在将树上路径最值转化为重构树。
0x20 虚树
虚树来解决树大小过大\(n,q\leqslant 10^5\)，由于\(\sum v_i\)一定不大，所以可以使用虚树解决。
0x21 引入
首先设立转移状态。由于切断根节点和询问点之间联系，只要砍掉这个点上任意一个祖先节点就可以，直接设\(f[i]\)表示当前节点为i，与其子树内任意询问点不连通的最小代价。
\[f[i]=\min(f[v],w_{i,v})
\]
注意，如果这个点本身为询问点，\(f[x]=inf\)。
由于每次重置整颗树的时间复杂度太高，考虑如何剪枝。由于有很多无用分枝，我们不关心其DP值，可以直接跳过；关心的，我们也可以通过化多边为一边简化状态。首先，我们发现如果一棵子树中有多个询问点，我们可以直接考虑将这些点合并，因为我们砍掉这一条边就能切断。将这些节点拎出来，发现他们可能是两点的LCA。这些点构成虚树。
0x22 构建虚树
0x221 通俗易懂的简单方法
没啥好说的，就是用栈模拟dfs的行为很难想到。
0x222 效率更高的复杂方法
可以看oi-wiki。
感觉增量法的思想还是挺妙的。。。
0x23 结论与技巧
第一个公式没咋遇见过。。。感觉只会在计算复杂度才用上。
第二个感觉很对！
0x24 例题
0x241 P2495 [SDOI2011] 消耗战
模板题。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std ;
#define ll long long
#define pii pair<int,int>
const int K = 18 ;
const int MAXN = 2.5e5+10 ;
const int INF = 1e9 ;
ll f[MAXN] ;
vector<pii> e[MAXN] ;
int n ,m ,lg[MAXN] ,k ,p[MAXN] ,mark[MAXN] ;
int idx ,dfn[MAXN] ,dep[MAXN] ,minn[K][MAXN] ,fa[K][MAXN] ,d[K][MAXN] ;
inline int get(int x , int y){return dep[x] < dep[y] ? x : y ;}
inline void dfs(int node , int ff){
dep[node] = dep[ff] + 1 ;
fa[0][node] = ff ;
dfn[node] = ++idx ;
minn[0][dfn[node]] = ff ;
for(pii i : e[node]){
int v = i.first ;if(v == ff) continue ;
dfs(v , node) ;
d[0][v] = i.second ;//切断1和这个点的代价
}
}
inline int LCA(int x , int y){
if(x == y) return x ;
if(dfn[x] > dfn[y]) swap(x , y) ;
int u = dfn[x] ,v = dfn[y] ,l = lg[v-u++] ;
return get(minn[l][u] , minn[l][v - (1<<l) + 1]) ;
}
inline int dist(int x , int a){//寻找两个点之间边代价最小
int ret = 1e9 ;
for(int i = lg[dep[x]-dep[a]];i >= 0;--i){
if(dfn[fa[i][x]] < dfn[a]) continue ;
ret = min(ret , d[i][x]) ;
x = fa[i][x] ;
}
return ret ;
}
inline bool cmp(int x , int y){return dfn[x] < dfn[y] ;}
inline void link(int u , int v){
if(mark[v]) f[v] = INF ;//如果这个点本身就是询问点：无穷大
f[u] += min((ll)dist(v , u) , f[v]) ;//否则观察是切这两个点之间的边还是切v点之前的边
}
int main(){
ios::sync_with_stdio(0) ;
cin >> n ; for(int i = 2;i <= n;++i) lg[i] = lg[i>>1] + 1 ;
for(int i = 1;i < n;++i){
int u ,v ,w ;cin >> u >> v >> w ;
e[u].push_back({v,w}) ;e[v].push_back({u,w}) ;
}
dfs(1,0) ;
for(int i = 1;i <= lg[n];++i)
for(int j = 1;j <= n;++j){
fa[i][j] = fa[i-1][fa[i-1][j]] ;//倍增求祖先
d[i][j] = min(d[i - 1][j] , d[i - 1][fa[i - 1][j]]) ;//倍增求最小代价
if(j + (1 << i) - 1 <= n) minn[i][j] = get(minn[i - 1][j] , minn[i - 1][j + (1 << (i - 1))]) ;//倍增求块内最小dfs序
}
cin >> m ;
while(m--){
cin >> k ;
for(int i = 1;i <= k;++i) cin >> p[i] ,f[p[i]] = 0 ,mark[p[i]] = 1 ;//f[i]表示节点i与其子树内任意询问点不连通的代价，mark[i]表示i号节点被询问
p[++k] = 1 ;//建立虚树时需要1号节点作为根节点
sort(p+1 , p+1+k , cmp) ;//按照遍历顺序进行排序
int stack[MAXN] ,top ;
stack[top=1] = p[1] ;//第一个放入根节点
for(int i = 2;i <= k;++i){
int lca = LCA(stack[top] , p[i]) ;//找到栈顶和当前节点的LCA
while(top > 1 && dep[lca] <= dep[stack[top-1]]) link(stack[top-1] , stack[top]) ,top-- ;//建边，出栈
if(lca != stack[top]) f[lca] = 0 ,link(lca , stack[top]) ,stack[top] = lca ;//发现LCA不在栈里：将LCA入栈
stack[++top] = p[i] ;//将当前节点入栈
}
for(int i = top-1;i;--i) link(stack[i] , stack[i+1]) ;//记得要出栈
for(int i = 1;i <= k;++i) mark[p[i]] = 0 ;//清空标记
cout << f[1] << '\n' ,f[1] = 0 ;//输出根节点与其子树内任意询问点不连通的最小代价
}
return 0 ;
}
0x242 P4103 [HEOI2014] 大工程
关键在状态转移。令\(siz[i]\)表示子树内关键点数量，距离最值\(maxx\minn\)。关键是第一问的答案。
按照每条边被计算了多少次。发现就是子树内的关键点分别向子树外的关键点连边的次数（因为每次走一定会经过这条边）。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std ;
#define ll long long
#define pii pair<int,int>
const int MAXN = 1e6+10 ;
const int K = 30 ;
vector<int> e[MAXN] ;
int n ,q ,k ,lg[MAXN] ,st[K][MAXN] ;
int idx ,dfn[MAXN] ,dep[MAXN] ,p[MAXN] ;
int siz[MAXN] ,maxx[MAXN] ,minn[MAXN] ;
inline int get(int x , int y){return dfn[x] < dfn[y] ? x : y ;}
inline void dfs(int node , int fa){
dep[node] = dep[fa] + 1 ;dfn[node] = ++idx ;
st[0][dfn[node]] = fa ;
for(int v : e[node]) if(v != fa) dfs(v , node) ;
}
inline int LCA(int x , int y){
if(x == y) return x ;
if((x = dfn[x]) > (y = dfn[y])) swap(x,y) ;
int d = lg[y-x++] ;
return get(st[d][x] , st[d][y-(1<<d)+1]) ;
}
ll ans1 ;int ans2 ,ans3 ;
inline void trans(int x , int y){
int delta = dep[y] - dep[x] ;
ans1 += 1ll * siz[y] * (k-siz[y])*delta ;
ans2 = min(ans2 , minn[x] + minn[y] + delta) ;
minn[x] = min(minn[x] , minn[y] + delta) ;
ans3 = max(ans3 , maxx[x] + maxx[y] + delta) ;
maxx[x] = max(maxx[x] , maxx[y] + delta) ;
siz[x] += siz[y] ;
}
inline bool cmp(int x , int y){return dfn[x] < dfn[y] ;}
int main(){
ios::sync_with_stdio(0) ;
cin >> n ;for(int i = 2;i <= n;++i) lg[i] = lg[i>>1] + 1 ;
for(int i = 1,u,v;i < n;++i){
cin >> u >> v ;
e[u].push_back(v) ;e[v].push_back(u) ;
}
dfs(1,0) ;
for(int i = 1;i <= lg[n];++i) for(int j = 1;j <= n;++j) st[i][j] = get(st[i-1][j] , st[i-1][j+(1 << (i-1))]) ;
cin >> q ;
while(q--){
cin >> k ;
for(int i = 1;i <= k;++i) cin >> p[i] ,siz[p[i]] = 1 ,minn[p[i]] = maxx[p[i]] = 0 ;
sort(p+1,p+1+k , cmp) ;
int stack[MAXN] ,top ;
stack[top=1]=p[1] ;
ans1 = 0 ;
ans2 = MAXN ,ans3 = 0 ;
for(int i = 2;i <= k;++i){
int lca = LCA(p[i] , stack[top]) ;
while(top > 1 && dfn[stack[top-1]] >= dfn[lca]) trans(stack[top-1] , stack[top]) ,top-- ;
if(lca != stack[top]){
minn[lca] = 1e9 ;maxx[lca] = siz[lca] = 0 ;trans(lca , stack[top]) ,stack[top] = lca ;
}
stack[++top] = p[i] ;
}
for(int i = top-1;i;--i)trans(stack[i] , stack[i+1]) ;
cout << ans1 << ' ' << ans2 << ' ' << ans3 << '\n' ;
}
return 0 ;
}
0x243 [模拟赛]山花
观察到gcd的操作很特殊。注意到如果一个节点和c的最大公因数是1在乘积中不会有任何贡献，这符合了虚树中有关于“大部分书上节点都没有用”这一著名论断。考虑只将有用的点拉下来建立虚树。由于需要计算两点之间间距，可以直接考虑树上差分。
0x244 CF986E Prince's Problem
和上面类似。
0x245 CF639F Bear and Chemistry【咕咕咕】
0x30 点分治
0x31 静态点分治
0x311 序列分治
分治法解决区间问题。
0x312 点分治
将“序列分治”的问题搬到了树上。我们将树的重心作为一棵树的“中点”，这是因为重心最大连通块大小不超过\(n\)，在使得达到折半效果的同时保证了分治树至多不超过\(\log n\)层。我们认为序列问题的三种情况中有两种都是子问题，所以我们考虑两个节点之间的简单路径要么经过根，要么不经过。看似后者不是前者的子问题，但实际上对于后者相当于过子树的根节点，依旧是子问题。
具体的，我们针对每一段树区间寻找重心，之后打上删除标记，遍历其的每一棵子树。像序列问题一样，我们不可以跨过已经被删除的点进行计算。
0x32 动态点分治
很难理解。但是已经学会。有注意事项但是不会。
0x33 性质与总结
很厉害。思维性很强。
0x34 例题
0x341 P3806 【模板】点分治1
模板题。
注意：
- 找重心前初始化
Root=0，放在for里面。 findroot()中子树大小为siz[v]。findroot()中求maxx[R]的最小值，注意符号。- 注意初始化
maxx[0]=N！！！ sort时候.end()后面不需要-1findroot()中更新maxx[node]时候用siz[v]。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std ;
#define pii pair<int,int>
#define fi first
#define se second
const int N = 1e4+5 ;
int n ,q ,k[N] ,ans[N] ,R ,vis[N] ,maxx[N] ,siz[N] ;
vector<pii> e[N] ;
inline void findroot(int node , int ff , int tot){//树的重心
siz[node] = 1 ,maxx[node] = 0 ;//记录子树大小，以及最大子树
for(pii i : e[node]){
int v = i.first ;if(v == ff || vis[v]) continue ;//发现是之前分治过的点就不在遍历
findroot(v , node , tot) ;
siz[node] += siz[v] ;
maxx[node] = max(siz[v] , maxx[node]) ;
}
maxx[node] = max(maxx[node] , tot-siz[node]) ;//由于是无根树，记得查看是哪边子树体积最大
if(maxx[node] < maxx[R]) R = node ;//更新树的重心
}
vector<pii> info ;
inline void getinfo(int node , int ff , int anc , int d){
info.push_back({d , anc}) ;//记录深度和初始节点
for(pii i:e[node]){
int v = i.first ;if(v == ff || vis[v]) continue ;
getinfo(v , node , anc , d+i.second) ;
}
}
inline void divide(int node){
vis[node] = 1 ;//首先删除重心节点
for(pii i : e[node]){
int v = i.first ;if(vis[v]) continue ;
getinfo(v , node , v , i.second) ;//分别遍历所有的连通块
}
info.push_back({0 , node}) ;//将重心节点也放入
sort(info.begin() , info.end()) ;//按照深度排序
for(int i = 1;i <= q;++i){//离线处理每一组询问
int l = 0 ,r = (int)info.size()-1 ;//初始化每一组边界
while(l < r && !ans[i]){
if(info[l].first + info[r].first > k[i]) r-- ;//深度过大，减小大深度
else if(info[l].first + info[r].first < k[i]) l++ ;//深度过小，增大小深度
else{
ans[i] = info[l].second != info[r].second ;//相当于区间两端位于重心两边
if(info[l].first == info[l+1].first) ++l ;//深度相同，可以平移
else --r ;//否则只能移动右侧
//实践证明l和r是可以互换的（最后一组if-else）
}
}
}
info.clear() ;
for(pii i:e[node]){
int v = i.first ;if(vis[v]) continue ;
R = 0 ;findroot(v , node , siz[v]) ;//每个子树都需要进行树分治
divide(R) ;//每个新的重心都需要遍历
}
}
int main(){
ios::sync_with_stdio(0) ;
cin >> n >> q ;
for(int i = 1,u,v,w;i < n;++i){
cin >> u >> v >> w ;
e[u].push_back({v , w}) ,e[v].push_back({u,w}) ;
}
for(int i = 1;i <= n;++i) cin >> k[i] ;//离线询问
maxx[0] = N ;//设为最大值
findroot(1,0,n) ;
divide(R) ;
for(int i = 1;i <= q;++i) cout << (ans[i] ? "AYE" : "NAY") << '\n' ;
return 0 ;
}
0x342 P6329 【模板】点分树 | 震波
模板题。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std ;
const int N = 1e5+10 ;
int n ,m ,fa[N] ,lg[N] ,val[N] ,idx ,dep[N] ,dfn[N] ,st[20][N] ;
vector<int> e[N] ,c1[N] ,c0[N] ;
//c0[x][d]表示x的点分树子树内与x原树距离<=d的节点权值和
//c1[x][d]表示x的点分树子树内与其父亲u原树距离<=d的节点权值和
inline void add(vector<int>&c , int x , int delta){
++x ;
while(x <= (int)c.size()) c[x-1] += delta ,x += x&-x;
}
inline int query(vector<int>&c , int x){
x = min(x+1 , (int)c.size()) ;
int ret = 0 ;
while(x) ret += c[x-1] ,x -= x&-x ;
return ret ;
}
inline int get(int x , int y){return dfn[x] < dfn[y] ? x : y ;}
inline void dfs(int node , int ff){
dep[node] = dep[ff] + 1 ;
st[0][dfn[node] = ++idx] = ff ;
for(int i:e[node]) if(i != ff) dfs(i , node) ;
}
inline int LCA(int x , int y){
if(x == y) return x ;
if((x = dfn[x]) > (y = dfn[y])) swap(x , y) ;
int d = lg[y-x++] ;
return get(st[d][x] , st[d][y-(1<<d)+1]) ;
}
int siz[N] ,maxx[N] ,R ,maxd ,las ;
bool vis[N] ;
inline void findroot(int node , int ff , int tot){
siz[node] = 1 ,maxx[node] = 0 ;
for(int v : e[node]){
if(v == ff || vis[v]) continue ;
findroot(v , node , tot) ;
siz[node] += siz[v] ;
maxx[node] = max(maxx[node] , siz[v]) ;
}
maxx[node] = max(maxx[node] , tot-siz[node]) ;
if(maxx[R] > maxx[node]) R = node ;
}
inline int dist(int x , int y){
return dep[x] + dep[y] - 2 * dep[LCA(x,y)] ;
}
inline void getdep(int node , int ff , int anc){
maxd = max(maxd , dist(node , anc)) ,siz[node] = 1 ;
for(int v:e[node]){
if(v == ff || vis[v]) continue ;
getdep(v , node , anc) ;
siz[node] += siz[v] ;
}
}
inline void divide(int node){
vis[node] = 1 ;
maxd = 0 ,getdep(node , 0 , node) ;
int tmp = maxd+1 ;
c0[node].resize(tmp) ;
for(int v:e[node]){
if(vis[v]) continue ;
R = 0 ,findroot(v , node , siz[v]) ;
c1[R].resize(tmp) ;
fa[R] = node ,divide(R) ;
}
}
inline void Add(int node , int delta){
int u = node ;
while(u){
add(c0[u] , dist(u , node) , delta) ;
if(fa[u]) add(c1[u] , dist(fa[u],node) , delta) ;
u = fa[u] ;
}
}
inline int Query(int node , int k){
int u = node ,ans = 0 ;
while(u){
if(dist(u , node) <= k) ans += query(c0[u] , k - dist(u , node)) ;
if(fa[u] && dist(fa[u] , node) <= k) ans -= query(c1[u] , k-dist(fa[u] , node)) ;
u = fa[u] ;
}
return ans ;
}
int main(){
ios::sync_with_stdio(0) ;
cin >> n >> m ,maxx[0] = N ;
for(int i = 1;i <= n;++i) cin >> val[i] ;
for(int i = 2;i <= n;++i) lg[i] = lg[i>>1] + 1 ;
for(int i = 1,u,v;i < n;++i) cin >> u >> v ,e[u].push_back(v) ,e[v].push_back(u) ;
dfs(1,0) ;
for(int i = 1;i <= lg[n];++i)
for(int j = 1;j + (1 << i) - 1 <= n;++j) st[i][j] = get(st[i-1][j] , st[i-1][j+(1<<(i-1))]) ;
findroot(1 , 0 , n) ,divide(R) ;
for(int i = 1;i <= n;++i) Add(i , val[i]) ;
for(int i = 1;i <= m;++i){
int opt ,x ,y ;cin >> opt >> x >> y ,x ^= las ,y ^= las ;
if(opt ^ 1) cout << (las = Query(x , y)) << '\n' ;
else Add(x , y - val[x]) ,val[x] = y ;
}
return 0 ;
}
0x343 P4149 [IOI2011] Race
在点分治过程中进行DP转移。
一开始直接在分治时取最值，但是发现在区间内进行双指针的时候往往只能取到一遍，从而无法正确的枚举到所有情况。例如我们要求长度为8的序列：
在l++移动时，我们无法完全取到对应的l不变，r--的所有情况。因此，这样枚举是不完整的。
这种情况下坚持使用二分是很不明智的。我们可以考虑使用另一种策略：对子树内部进行遍历。
0x344 P2634 [国家集训队] 聪聪可可
关键点在于将三种模数进行抽象。
0x345 P4178 Tree
例0x343要求具体将所有数枚举出来，求最小值，就不可做。但是这道题要求统计方案数，所以就可以双指针统计。
0x347 P4075 [SDOI2016] 模式字符串
DP和哈希的综合题。感觉很妙。
0x348 CF914E Palindromes in a Tree
和状压相结合。自己没独立想出来。
0x349 P3345 [ZJOI2015] 幻想乡战略游戏【咕咕咕】
0x34A AT_cf17_final_j Tree MST【咕咕咕】
0x34B P6199 [EER1] 河童重工【咕咕咕】
0x34C CF150E Freezing with Style【咕咕咕】
0x40 长链剖分
0x41 算法简介与性质
就是将子树深度作为重儿子。
好像就是性质二有点用处。
0x42 应用：树上k级祖先
关键就是预处理。使用倍增查询。
0x43 应用：优化深度相关的DP
0x431 一般形式
与树上DP的深度有关的DP都可以优化。
一般形式：\(f[i][j]\)表示以i为根的子树内，深度为j的节点的贡献。
0x432 CF1009F Dominant Indices
考虑重儿子数量小于轻儿子数量，但是转移代价却很大。对于重儿子，我们直接继承他的答案，然后将轻儿子的答案合并过来。
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
#define ll long long
#define MAX 1001000
inline int read()
{
int x=0;bool t=false;char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
if(ch=='-')t=true,ch=getchar();
while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
return t?-x:x;
}
struct Line{int v,next;}e[MAX<<1];
int h[MAX],cnt=1;
inline void Add(int u,int v){e[cnt]=(Line){v,h[u]};h[u]=cnt++;}
int n,md[MAX],dep[MAX],hson[MAX],ans[MAX];
void dfs1(int u,int ff)
{
dep[u]=md[u]=dep[ff]+1;
for(int i=h[u];i;i=e[i].next)
{
int v=e[i].v;if(v==ff)continue;
dfs1(v,u);md[u]=max(md[u],md[v]);
if(md[v]>md[hson[u]])hson[u]=v;
}
}
int tmp[MAX],*f[MAX],*id=tmp;
void dfs(int u,int ff)
{
f[u][0]=1;
if(hson[u])f[hson[u]]=f[u]+1,dfs(hson[u],u),ans[u]=ans[hson[u]]+1;
for(int i=h[u];i;i=e[i].next)
{
int v=e[i].v;if(v==ff||v==hson[u])continue;
f[v]=id;id+=md[v]-dep[v]+1;dfs(v,u);
for(int j=0;j<=md[v]-dep[v];++j)
{
f[u][j+1]+=f[v][j];
if(f[u][j+1]>f[u][ans[u]]||(f[u][j+1]==f[u][ans[u]]&&ans[u]>j+1))
ans[u]=j+1;
}
}
if(f[u][ans[u]]==1)ans[u]=0;
}
int main()
{
n=read();
for(int i=1;i<n;++i)
{
int u=read(),v=read();
Add(u,v);Add(v,u);
}
dfs1(1,0);f[1]=id;id+=md[1];dfs(1,0);
for(int i=1;i<=n;++i)printf("%d\n",ans[i]);
return 0;
}
0x433 注意点与技巧
尝试使用指针。
0x44 经典结论
非常经典的结论：选一个节点能覆盖它到根的所有节点。选\(k\)个节点，覆盖的最多节点数就是前\(k\)条长链长度之和，选择的节点即\(k\)条长链末端。
0x45 例题
0x451 P4292 [WC2010] 重建计划【咕咕咕】
不会0/1分数规划，先咕咕咕了。
0x452 P5903 【模板】树上 k 级祖先
#include<iostream>
#include<cstdio>
#include<vector>
using namespace std ;
#define ll long long
#define ui unsigned int
const int N = 5e5+10 ;
int n ,q ,rt ,lg[N] ,d[N] ,f[N][20] ,son[N] ,dep[N] ,top[N] ,lans ;
ui s ;
ll ans ;
vector<int> e[N] ,u[N] ,v[N] ;
inline ui get(ui x){return x ^= x << 13 ,x ^= x >> 17 ,x ^= x << 5 ,s = x ;}
inline void dfs1(int x){
dep[x] = d[x] = d[f[x][0]] + 1 ;
for(int i:e[x]){
f[i][0] = x ;
for(int j = 0;f[i][j];++j) f[i][j+1] = f[f[i][j]][j] ;
dfs1(i) ;
if(dep[i] > dep[x]) dep[x] = dep[i] ,son[x] = i ;
}
}
inline void dfs2(int x , int p){
top[x] = p ;
if (x == p){
for(int i = 0,o = x;i <= dep[x] - d[x];++i)
u[x].push_back(o) ,o = f[o][0] ;
for(int i = 0,o = x;i <= dep[x] - d[x];++i)
v[x].push_back(o) ,o = son[o] ;
}
if(son[x]) dfs2(son[x], p) ;
for(int y : e[x]) if (y != son[x]) dfs2(y, y) ;
}
inline int ask(int x , int k){
if (!k) return x ;
x = f[x][lg[k]] ,k -= 1 << lg[k] ,k -= d[x] - d[top[x]] ,x = top[x] ;
return k >= 0 ? u[x][k] : v[x][-k] ;
}
int main(){
ios::sync_with_stdio(0) ;
cin >> n >> q >> s ;
for(int i = 1;i <= n;++i) cin >> f[i][0] ,e[f[i][0]].push_back(i) ;
for(int i = 2;i <= n;++i) lg[i] = lg[i>>1]+1 ;
rt = e[0][0] ;dfs1(rt) ;dfs2(rt , rt) ;
for(int i = 1 ,x ,k;i <= q;++i){
x = (get(s) ^ lans) % n + 1 ;
k = (get(s) ^ lans) % d[x] ;
ans ^= 1ll * i * (lans = ask(x , k)) ;
}
cout << ans ;
return 0 ;
}
0x453 CF490F Treeland Tour
