树的直径（树的最长路）

1.两次dfs找两端（无负边权）

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
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1010, M = 1010;
int h[N], e[M], w[M], nxt[M], eidx, p, d[N], ans;
void add(int u, int v, int weight){   // 添加有向边 u->v, 权重为weight
    e[eidx] = v;        			  // 记录边的终点
    w[eidx] = weight;                 // 记录边的权重
    nxt[eidx] = h[u];                 // 将下一条边指向结点u此时的第一条边
    h[u] = eidx;                      // 将结点u的第一条边的编号改为此时的eidx
    eidx++;                           // 递增边的编号edix, 为将来使用
}
void dfs(int u,int fa){//fa代表父节点，从0开始代表从u走找一条最长路 
	int i,id;
	if(ans<d[u]){
		ans=d[u];
		p=u;
	}
	for(int i=h[u];i!=-1;i=nxt[i]){
		id=e[i];
		if(id==fa)
		continue;
		d[id]=d[u]+w[i];
		dfs(id,u);//找u的子节点
	}
}
signed main(){
	int n,m;
	cin>>n>>m;
	memset(h,-1,sizeof(h));//表头数组设-1的习惯 
	while(m--){
		int u,v,wei;
		cin>>u>>v>>wei;
		add(u,v,wei);
		add(v,u,wei);
	}
	ans=0;
	d[1]=0;
	dfs(1,0);//目的是通过第一次dfs找到树直径的一端，即求p 
	ans=0;
	d[p]=0;
	//cout<<p<<endl;
	dfs(p,0);
	cout<<ans<<endl;
	return 0;
}

2.树形dp（找距离和次远距离和的最大值）

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
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1010, M = 1010;
int h[N], e[M], w[M], nxt[M], eidx, p, d[N], dc[N], ans;
void add(int u, int v, int weight){
    e[eidx] = v;
    w[eidx] = weight;
    nxt[eidx] = h[u];
    h[u] = eidx;
    eidx++;
}
void dfs(int u,int fa){
	int i,id;
	if(ans<d[u]){
		ans=d[u];
		p=u;
	}
	for(int i=h[u];i!=-1;i=nxt[i]){
		id=e[i];
		if(id==fa)
		continue;
		dfs(id,u);//先求出距离才能dp，所以先dfs 
		if(w[i]>d[u]){
			dc[u]=d[u];
			d[u]=w[i];
		}else if(w[i]>dc[u]){
			dc[u]=w[i];
		}
		ans=max(ans,d[u]+dc[u]);
	}
}
signed main(){
	int n,m;
	cin>>n>>m;
	memset(h,-1,sizeof(h));
	while(m--){
		int u,v,wei;
		cin>>u>>v>>wei;
		add(u,v,wei);
		add(v,u,wei);
	}
	dfs(1,0);
	cout<<ans<<endl;
	return 0;
}

lca最近公共祖先

1.Tarjan离线算法o(n+q询问次数)

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
#include<bits/stdc++.h>
#define memset(a,v) memset(a,v,sizeof(a))
using namespace std;
typedef long long int LL;
const int MAXL(1e4);
int father[MAXL+50];
bool is_root[MAXL+50];
bool vis[MAXL+50];
vector<int>v[MAXL+50];
int root;
int cx,cy;
int ans;
int Find(int x){//并查集路径压缩查询 
    if(x!=father[x])
        father[x]=Find(father[x]);
    return father[x];
}
void Join(int x,int y){//并查集合并 
    int fx=Find(x),fy=Find(y);
    if(fx!=fy)
        father[fy]=fx;
}
void LCA(int u){//离线算法即一次dfs就能解决所有询问 
    for(int i=0; i<v[u].size(); i++){
        int child=v[u][i];
        if(!vis[child]){
            LCA(child);
            Join(u,child);
            vis[child]=true;
        }
    }
    if(u==cx&&vis[cy]==true)
        ans=Find(cy);
    if(u==cy&&vis[cx]==true)
        ans=Find(cx);
}
void init(){
    memset(is_root,true);
    memset(vis,false);
    int n;
    scanf("%d",&n);
    for(int i=0; i<=n; i++)
        v[i].clear();
    for(int i=1; i<=n; i++)
        father[i]=i;
    for(int i=1; i<n; i++){
        int x,y;
        scanf("%d%d",&x,&y);
        v[x].push_back(y);
        is_root[y]=false;
    }
    scanf("%d%d",&cx,&cy);
    for(int i=1; i<=n; i++){
        if(is_root[i]==true){//找出根节点 
            root=i;
            break;
        }
    }
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--){
        init();
        LCA(root);//从根节点开始处理 
        cout<<ans<<endl;
    }
}

2.倍增算法 o(n*log(n))

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
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int INF = 0x3f3f3f;
const int MAXN = 1e4 + 5;
const int MAXLOG = log(2, MAXN);
int fa[MAXN], dep[MAXN], f[MAXN][MAXLOG];
vector<int> G[MAXN];
void dfs(int node, int k){//父节点node和深度k
	dep[node] = k;
	for(int i = 0; i < G[node].size(); i++){
		dfs(G[node][i], k + 1);
	}
}
void getf(){//预处理父节点数组 
	for(int node = 1; node <= n; i++){
		f[node][0] = fa[node];
		for(int i = 1; i <= log(2, n); i++){
			f[node][i] = f[f[node][i - 1]][i - 1];
		}
	}
}
int lca(int u, int v){
	if(u == v)return u;
	return lca(fa[u], fa[v]);
}
signed main(){
	memset(fa, -1, sizeof fa);
	getf();
	int n, root;
	cin >> n;
	for(int i = 1; i < n; i++){
		int u, v;
		cin >> u >> v;
		fa[v] = u;
		G[u].push_back(v);
	}
	for(int i = 1; i <= n / 2 + 1; i++){//可以任选一个根节点，注意题目信息 
		if(fa[i] == -1){
			root = i;
			break;
		}
		if(fa[n - i] == -1){
			root = n - i;
			break;
		}
	}
	dfs(root, 0);
	int u, v;
	cin >> u >> v;//这里只查了一次，据题更改 
	for(int k = log(2, dep[u]); dep[u] >= dep[v]; k--){//二进制优化使一次查询logn 
	    if(dep[u] - (1 << k) >= dep[v]){
	    	dep[u] -= (1 << k);
	    	u = f[u][k];
	    }
	}
	for(int k = log(2, dep[v]); dep[v] >= dep[u]; k--){
	    if(dep[v] - (1 << k) >= dep[u]){
	    	dep[v] -= (1 << k);
	    	v = f[v][k];
	    }
	}
	cout << lca(u, v) << endl;
	return 0;
}

树的重心

对于树上的每一个点，计算其所有子树中最大的子树节点数，这个值最小的点就是这棵树的重心

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
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=110000;
int h[N],ne[2*N],e[2*N],idx,size[N],wei[N],n,m,st;
void add(int a,int b){
	e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void dfs(int u,int fa){
	size[u]=1;
	wei[u]=1;
	for(int i=h[u];i!=-1;i=ne[i]){
		if(e[i]!=fa){
			dfs(e[i],u);
			size[u]+=size[e[i]];
			wei[u]=max(wei[u],size[e[i]]);
		}
	}
	wei[u]=max(wei[u],n-size[u]);
	if(wei[u]<wei[st])
	st=u;
}
signed main(){
	memset(h,-1,sizeof(h));
	cin>>n>>m;
	for(int i=0;i<m;i++){
		int a,b;
		cin>>a>>b;
		add(a,b);
		add(b,a);
	}
	wei[0]=0x3f3f3f3f;
	dfs(1,0);
	cout<<st<<"的子树节点有"<<wei[st]<<endl;
	return 0;
}

树上点差分（P3128）

修改k个路径，每个u到v上所有点点权加1，求最大点权的点

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
#include<bits/stdc++.h>
using namespace std;
const int N=50005;
int max0;
vector<int> vec[N]; 
int fa[N][20], dep[N],dlt[N]; 
int ans = 0; 
void dfs(int x){
    for(int i = 1;i <= max0;i++){
        fa[x][i]=fa[fa[x][i-1]][i-1];
    } 
    for(int i = 0; i < vec[x].size();i++){
    	int u = vec[x][i];
        if(u != fa[x][0]){
            fa[u][0] = x;
            dep[u] = dep[x] + 1;
            dfs(u);
        }
    }
}
int LCA(int u,int v){//要从最近公共祖先处做差分 
    if(dep[u] < dep[v]) swap(u,v);
    int delta = dep[u] - dep[v];
    for(int x = 0;x <= max0;x++){
        if((1 << x) & delta)
            u = fa[u][x];
    }
    if(u == v) return u;
    for(int x = max0;x >= 0;x--)
        if(fa[u][x] != fa[v][x]){
			u = fa[u][x];
            v = fa[v][x];
        }
    return fa[u][0];
}
void dfs_cnt(int x){//回溯前缀和，找到最大的点权
	for(int i = 0; i < vec[x].size(); i++){
		int v = vec[x][i];
		if(v != fa[x][0]){
			dfs_cnt(v);
			dlt[x] += dlt[v];
		}
		ans = max(ans, dlt[x]);
	}
}
int main(){
	int n,k;
	cin >> n >> k;
	max0 = log2(n);
	for(int i = 0; i < n - 1; i++){
		int a,b;
		scanf("%d%d",&a,&b);
		vec[a].push_back(b);
		vec[b].push_back(a);
	}
	dfs(1);
	for(int j = 0; j < k; j++){
		int a,b;
		scanf("%d%d",&a,&b);
		int c = LCA(a,b);
		dlt[c]--,dlt[fa[c][0]]--;//树上的点差分 
		dlt[a]++,dlt[b]++;
	}
	dfs_cnt(1);
	cout << ans << endl;
	return 0;
}

树链剖分

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
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
//操作 1： 格式： 1 x y z 表示将树从 x 到 y 结点最短路径上所有节点的值都加上 z
//操作 2： 格式： 2 x y 表示求树从 x 到 y 结点最短路径上所有节点的值之和
//如果只有上述两种操作可以直接为树上差分
//操作 3： 格式： 3 x z 表示将以 x 为根节点的子树内所有节点值都加上 z
//操作 4： 格式： 4 x 表示求以 x 为根节点的子树内所有节点值之和
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
int dep[maxn], fa[maxn], siz[maxn], son[maxn];//深度 父亲 子树大小 重儿子是
int id[maxn], top[maxn], rk[maxn];//dfs 序后点新编号 节点链的顶端 序号 x 的点
int n, m, r, mod, rt, cnt;//cnt 用到了两次 注意清空
int head[maxn], v[maxn];
struct edge{
	int next, to; 
}e[maxn * 2];
struct node{
	int l, r, sum, lazy;
}t[maxn << 2];
void add(int x, int y){
	e[++cnt].next = head[x];
	e[cnt].to = y;
	head[x] = cnt;
}
inline void dfs1(int u, int f, int deep){//u 当前节点 ,f 父亲，deep 深度
	dep[u] = deep;//标记每个点的深度
	fa[u] = f;//标记每个点的父亲
	siz[u] = 1;//标记每个非叶子节点的子树大小
	int maxson = -1;
	for (int i = head[u]; i; i = e[i].next){
		int v = e[i].to;
		if (v == f) continue;//为父亲
		dfs1(v, u, deep + 1);
		siz[u] += siz[v];//把他的儿子数加到他身上
		if (siz[v] > maxson) son[u] = v, maxson = siz[v];
		//标记每个非叶子节点的重儿子编号
	}
}//dfs1(root,0,1);
inline void dfs2(int u, int topf){//x 当前节点 ，topf 当前链的最顶端的节点
	id[u] = ++cnt;//标记每个点的新编号
	rk[cnt] = u;//序号 cnt 对应节点 u
	top[u] = topf;//每个点所在链的顶端
	if (!son[u]) return;//如果没有儿子则返回
	dfs2(son[u], topf);//按先处理重儿子，在处理轻儿子的顺序递归处理
	for (int i = head[u]; i; i = e[i].next){
		int v = e[i].to;
		if (v == fa[u] || v == son[u]) continue;
		dfs2(v, v);//对于每一个轻儿子都有一条从他自己开始的链
	}
}
inline void pushup(int x){ t[x].sum = (t[x<<1].sum + t[x<<1|1].sum); }
void build(int l, int r, int rt){
	t[rt].l = l, t[rt].r = r, t[rt].sum = t[rt].lazy = 0;
	if (l == r){
		t[rt].sum = v[rk[l]];
		return;
	}
	int mid = l + r >> 1;
	build(l, mid, rt<<1), build(mid + 1, r, rt<<1|1);
	pushup(rt);
}
inline int len(int x){ return t[x].r - t[x].l + 1; }//存在结构体里？？
inline void pushdown(int x){//下传懒惰标记
	if (t[x].lazy){
	int ls = (x<<1), rs = (x<<1|1), lz = t[x].lazy;
	t[ls].lazy += lz; t[rs].lazy += lz;
	t[ls].sum += lz*(len(ls)); t[rs].sum += lz*(len(rs));
	t[x].lazy = 0;
	}
}
void update(int l, int r, int c, int x){
	if (t[x].l >= l&&t[x].r <= r){
	t[x].lazy += c; t[x].sum += len(x)*c;
	return;
	}
	pushdown(x);
	int mid = (t[x].l + t[x].r) >> 1;
	if (mid >= l) update(l, r, c, x<<1);
	if (r > mid) update(l, r, c, x<<1|1);
	pushup(x);
}
int query(int l, int r, int rt){
	if (t[rt].l >= l&&t[rt].r <= r) return t[rt].sum;
	pushdown(rt);
	int mid = (t[rt].l + t[rt].r) >> 1, tot = 0;
	if (mid >= l) tot += query(l, r, rt<<1);
	if (r > mid) tot += query(l, r, rt<<1|1);
	return tot;
}
inline int sum(int x, int y){//求（x,y）路径的权值之和
	int ans = 0;
	while (top[x] != top[y]){//两点不在同一条重链
		if (dep[top[x]] < dep[top[y]]) swap(x, y);
		ans += query(id[top[x]], id[x], 1);
		x = fa[top[x]];
	}
//循环结束 两点位于同一重链上 但两点不一定为同一点 还要统计这两点直接贡献
	if (id[x]>id[y]) swap(x, y);
	ans += query(id[x], id[y], 1);
	return ans;
}
inline void updates(int x, int y, int c){//更新路径上的权值
	while (top[x] != top[y]){
		if (dep[top[x]] < dep[top[y]]) swap(x, y);
		update(id[top[x]], id[x], c, 1);
		x = fa[top[x]];
	}
	if (id[x]>id[y]) swap(x, y);
	update(id[x], id[y], c, 1);
}
int main(){
	scanf("%lld%lld%lld", &n, &m, &r);
	for (int i = 1; i <= n; i++) scanf("%lld", &v[i]);
	for (int x, y, i = 1; i < n; i++){
		scanf("%d%d", &x, &y);
		add(x, y), add(y, x);
	}
	cnt = 0; dfs1(r, 0, 1), dfs2(r, r);
	build(1, n, 1);
	for (int op, x, y, k, i = 1; i <= m; i++){
		scanf("%d", &op);
		if (op == 1){//将 x->y 路径上的点都加上 k
			scanf("%d%d%d", &x, &y, &k);
			updates(x, y, k);
		}else if (op == 2){//求 x->y 路径上的点的权值总和
			scanf("%d%d", &x, &y);
			printf("%d\n", sum(x, y));
		}else if (op == 3){//将以 x 为根节点的子树内所有节点值都加上 y
			scanf("%d%d", &x, &y);
			update(id[x], id[x] + siz[x] - 1, y, 1);
		}else{//求以 x 为根节点的子树内所有节点值之和
			scanf("%d", &x);
			printf("%d\n", query(id[x], id[x] + siz[x] - 1, 1));
		}
	}
}