CCF-202212-4-聚集方差

Kelvin
  2023-02-27 2023-02-27 00 Created   2023-05-11 21:41:13 2023-05-11 21:41 Updated      

题目

202212-4 聚集方差

前置知识

链式前向星

作用: 存储图
存储图的方法:
邻接表如下图所示:
邻接表
缺点: 邻接表用数据结构不好表示
比如邻接表用vector<Node>数组表示
改进: 链式前向星
邻接表用int数组代替

结点表示
1
2
3
4
5
6
// 存储边的信息
struct{
    int to, w, next;
}Edge[maxm];
// Head[i]存储点i的第一条边的index
int tot, Head[maxn];

链式前向星

添加
1
2
3
4
5
6
inline void AddEdge(int u, int v, int w){
    Edge[tot].to = v;
    Edge[tot].w = w;
    Edge[tot].next = Head[u];
    Head[u] = tot++;
}

链式前向星添加过程

dfs序

#144.DFS 序1
思路: 链式前向星存储图,dfs遍历生成dfs序(int dfn[]),并记录每个结点及其子结点序列的左右端点(int l[], int r[]).当求结点i子树上所有结点的权值之和即为求l[i]到r[i]的w和.

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
#include<bits/stdc++.h>
typedef long long LL;
using namespace std;
const int MAXN = 1e6+10;
const int MAXM = 2e6+10; 
LL w[MAXN];
// N结点个数, R根结点index, M操作组数 
int N,M,R; 
struct Edge{
	int to,next=0;
}es[MAXM];
int tot = 1;
int head[MAXN]={0};
int iindex = 1; 
int dfn[MAXN]={0};
int l[MAXN]={0};
int r[MAXN]={0};
LL sum[MAXN]={0};
void init(){
	fill(head,head+N,0);
}

//void getPreSum(){
//	for(int i = 1;i<=N;i++){
//		sum[i]=sum[i-1]+w[dfn[i]];
//	}
//}
//链式前向星构建树 
void buildTree(){
	for(int i = 1;i<=N-1;i++){
		int u,v;
		scanf("%d %d",&u,&v);
		es[tot].to = v;
		es[tot].next = head[u];
		head[u]=tot++;
		es[tot].to = u;
		es[tot].next = head[v];
		head[v]=tot++;
	}	
}
//生成dfs序 
void dfs(int u, int f){
	// printf("*****%d\n",u);
	dfn[iindex]=u;
	l[u]=iindex;
	iindex++; 
	for(int i = head[u];i!=0;i=es[i].next){
		if(es[i].to!=f) dfs(es[i].to, u);
	}
	r[u]=iindex-1; 
}
void op1(int a,int x){
	
	w[a]+=x;
	//getPreSum();
}
void op2(int a){
	LL sum1 = 0;
	for(int i = l[a];i<=r[a];i++){
		sum1+=w[dfn[i]];
	}
	printf("%lld\n",sum1);
}
int main(){
	init();
	scanf("%d %d %d",&N,&M,&R);
	for(int i = 1;i<=N;i++){
		scanf("%lld", &w[i]); 
	}
	buildTree(); 
	dfs(R,-1);
	//getPreSum();
//	for(int i = 1;i<=N;i++){
//		printf("%d ",sum[i]);
//	}
	for(int i = 0;i<M;i++){
		int op;
		scanf("%d",&op);
		if(op==1){
			int a,x;
			scanf("%d %d",&a,&x);
			op1(a,x);
		}else{
			int a;
			scanf("%d",&a);
			op2(a);
		}
	}
	return 0;
}

优化:
求和部分可以使用树状数组优化.

树状数组/二叉索引树(Binary Indexed Tree)

应用:单点修改+区间查询
下标从1开始.
树状数组

lowbit
1
2
3
int lowbit(int i){
    return i&-i;
}

lowbit()返回i的二进制表示1的最低位对应的权值
比如
i=1110,i&(-i)=0010
i=1100,i&(-i)=0100

update
1
2
3
4
5
6
void update(int i, int val){
    while(i<=n) {
        c[i]+=val;
        i+=lowbit(i);
    }
}
sum
1
2
3
4
5
6
7
8
int sum(int i){
    int ret = 0;
    while(i>0){
        ret+=c[i];
        i-=lowbit(i);
    }
    return ret;
}
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
#include<bits/stdc++.h>
typedef long long LL;
#define re register
using namespace std;
const int MAXN = 1e6+10;
const int MAXM = 2e6+10; 
LL c[MAXN];
LL w[MAXN];
// N结点个数, R根结点index, M操作组数 
int N,M,R; 
struct Edge{
	int to,next=0;
}es[MAXM];
int tot = 1;
int head[MAXN]={0};
int iindex = 1; 
int l[MAXN]={0};
int r[MAXN]={0};
LL sum[MAXN]={0};

inline int lowbit(int i){
	return i&(-i);
}
inline void add(int i, LL val){
	while(i<=N){
		c[i]+=val;
		i+=lowbit(i);
	}
}
inline LL sumT(int i){
	LL res = 0;
	while(i>=1){
		res += c[i];
		i-=lowbit(i);
	}
	return res;
}

void buildTree(){
	for(re int i = 1;i<=N-1;i++){
		int u,v;
		scanf("%d %d",&u,&v);
		es[tot].to = v;
		es[tot].next = head[u];
		head[u]=tot++;
		es[tot].to = u;
		es[tot].next = head[v];
		head[v]=tot++;
	}	
}
//生成dfs序 
void dfs(int u, int f){
	add(iindex, w[u]);
	l[u]=iindex;
	iindex++; 
	for(re int i = head[u];i!=0;i=es[i].next){
		if(es[i].to!=f) dfs(es[i].to, u);
	}
	r[u]=iindex-1; 
}
inline void op1(int a,int x){
	add(l[a],x);
	// w[a]+=x;
	//getPreSum();
}

inline void op2(int a){
	printf("%lld\n",sumT(r[a])-sumT(l[a]-1));
}

int main(){
	scanf("%d %d %d",&N,&M,&R);
	for(int i = 1;i<=N;i++){
		scanf("%lld", &w[i]); 
	}
	buildTree(); 
	dfs(R,0);
	for(re int i = 0;i<M;i++){
		int op;
		scanf("%d",&op);
		if(op==1){
			int a,x;
			scanf("%d %d",&a,&x);
			op1(a,x);
		}else{
			int a;
			scanf("%d",&a);
			op2(a);
		}
	}
	return 0;
}

树链剖分

洛谷P3379
应用:求LCA(最近公共祖先)
核心:两次dfs,第一次dfs标出dep深度,siz子节点个数,fa父节点,son重儿子等信息,第二次dfs标出top重链顶端结点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void dfs1(int x){
	siz[x]=1;
	dep[x]=dep[f[x]]+1;
	for(int i = head[x];i;i=e[i].ne) {
		int dd = e[i].to;
		if(dd==f[x]) continue;
		f[dd]=x;
		dfs1(dd);
		siz[x]+=siz[dd];
		if(!son[x]||siz[son[x]]<siz[dd]) son[x]=dd;
	}
}

void dfs2(int x,int tv){
	top[x]=tv;
	if(son[x]) dfs2(son[x], tv);
	for(int i = head[x];i;i=e[i].ne){
		int dd = e[i].to;
		if(dd==f[x]||dd==son[x]) continue;
		dfs2(dd, dd);
	}
}

dsu on tree

  • Title: CCF-202212-4-聚集方差
  • Author: Kelvin
  • Created at: 2023-02-27 00:00:00
  • Updated at: 2023-05-11 21:41:13
  • Link: https://yanwc.com/2023/02/27/2023-03-09-ccf-202212-4/
  • License: This work is licensed under CC BY-NC-SA 4.0.
On this page
CCF-202212-4-聚集方差
  1. 题目
  2. 前置知识