树论-静态点分治
点分治，是一种针对树上简单路径统计问题的算法。
例题
题目描述
给定一棵有 \(n\) 个点的树，询问树上距离为 \(k\) 的点对是否存在。
做法
对于整棵树的一个根 \(rt\) 来说，路径可以分为两种，经过 \(rt\) 的路径和不经过 \(rt\) 的路径。
其中设路径的端点为 \((u,v)\) 。
对于第一种路径来说，路径长度就为 \(dis(u,rt)+dis(v,rt)\) ，所以可以预处理出来 \(dis[u]\) 数组，表示 \(u\) 到 \(rt\) 的距离。
对于第二种路径来说，它不经过 \(rt\) ，那么它就包含在 \(rt\) 的某棵子树内，那么就可以找到这颗子树的根，再对它求一次，第一种路径。
也就是说，把整棵树分成许多子树，对每棵子树分别求解第一种路径，随后继续将子树分下去…
所以时间复杂度会与分子树时的递归层数 \(T\) 有关，且每一层的所有递归过程合计对每个点处理一次，所以时间复杂度为 \(O(T * n)\) 。
如果这棵树退化成一条链时， \(T=n\) ，复杂度为 \(O(n^2)\) 。
为了让 \(T\) 减小，所以将子树的重心作为子树的根进行处理，此时 \(T=\log n\) ，总复杂度为 \(O(n\log n)\) 。
这就是点分治！
点分治的时候，不会出现重复的点对。
那么对于本题来说，询问可以离线处理。
具体的细节还是看代码吧！
code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114 | #include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e4+10;
int read(){//快读
int r=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
r=(r<<3)+(r<<1)+(ch-'0');
ch=getchar();
}
return r*f;
}
int n,m;
struct node {
int t,w;
node(int a,int b) {
t=a,w=b;
}
};
vector<node>v[N];
int si[N],v1[N],msi[N],rt,cnt;
//si[s]:以s为根的子树大小 v1:这个点在点分治过程中是否遍历 msi[s]:表示删除结点s后产生的子树中，最大的那棵的大小
//rt:重心 cnt:这棵树大小
void dfs(int s,int fa) {//找重心
si[s]=1;
msi[s]=0;
for(int i=0; i<v[s].size(); i++) {
int y=v[s][i].t;
if(y==fa||v1[y])continue;
dfs(y,s);
si[s]+=si[y];
msi[s]=max(msi[s],si[y]);
}
msi[s]=max(msi[s],cnt-si[s]);
if(msi[s]<msi[rt])rt=s;
}
int q[N],d[N];//d:到根的距离
int ma[10000010],maa[N],tot;//存之前已经处理完的子树的信息:距离
vector<int>vv;
bool fl[N];//fl:是否有这个距离的路径
void dfs1(int s,int fa) {//处理这颗子树的所有点到根距离
vv.push_back(d[s]);//这颗子树的所有距离
for(int i=0;i<v[s].size();i++){
int y=v[s][i].t;
int w=v[s][i].w;
if(y==fa||v1[y])continue;
d[y]=d[s]+w;
dfs1(y,s);
}
}
inline void solve(int s,int fa){
tot=0;
for(int i=0;i<v[s].size();i++){
int y=v[s][i].t;
int w=v[s][i].w;
if(y==fa||v1[y])continue;
vv.clear();
d[y]=w;
dfs1(y,s);//对于每棵子树进行处理距离
for(int j=0;j<vv.size();j++){
for(int k=1;k<=m;k++){
if(q[k]>=vv[j]){
fl[k]|=ma[q[k]-vv[j]];
}
}
}
for(int j=0;j<vv.size();j++){
if(vv[j]<=10000000)maa[++tot]=vv[j],ma[vv[j]]=1;
}
}
for(int i=1;i<=tot;i++){
ma[maa[i]]=0;
maa[i]=0;
}
//最后要清空
}
void dianfenzhi(int s,int fa) {//点分治
v1[s]=1;//这个点已被遍历
ma[0]=1;//距离为0肯定是存在的
solve(s,fa);//处理
for(int i=0; i<v[s].size(); i++) {
int y=v[s][i].t;
if(y==fa||v1[y])continue;
cnt=si[y];
rt=0;
msi[rt]=1e15;
dfs(y,0);//找重心
dianfenzhi(rt,0);//继续点分治
}
}
signed main() {
n=read(),m=read();
for(int i=1; i<n; i++) {
int x,y,z;
x=read(),y=read(),z=read();
v[x].push_back(node(y,z));
v[y].push_back(node(x,z));
}
for(int i=1; i<=m; i++)q[i]=read();//离线
msi[rt]=1e15;
cnt=n;
dfs(1,0);//先找重心
dianfenzhi(rt,0);//点分治
for(int i=1; i<=m; i++) {
if(fl[i])cout<<"AYE\n";
else cout<<"NAY\n";
}
return 0;
}
|
题单
板题，对于 \(\%3\) 后的数进行储存，然后算贡献就行了。
板题，再统计一下边的数量就行了。
搞棵树状数组就行了。
发现拼路径的时候不仅需要知道根到点的权值之和，还需要记录边的数量以及与根相连的边的颜色。
首先处理与根相连的边的颜色：考虑排序，将每种颜色依次处理。
然后以边数为下标建立两棵线段树，第一棵线段树记录与现在颜色不同的权值最大值，第二棵线段树记录与现在颜色相同的权值最大值。
最后算一下贡献就行了，复杂度 \(O(n \log^2 n)\) 。
使用单调队列可以将复杂度降到 \(O(n \log n)\) 。
未完待续？