DFS序专题

NC13611 https://ac.nowcoder.com/acm/problem/13611

题意：要求树上任意两点相同颜色之间的路径上的点也是相同颜色，k种颜色，求方案数

Solution：原问题等价于将树分割成若干连通块且相互之间颜色不同

其实是道数论题。 题意可以转化为将树分割为不超过 kk 个连通块，每个连通块颜色不同。若将树分割为 ii 个连通块，则需要删去 i−1i-1 条边，故方案数为 Cn−1i−1\mathrm{C}_{n-1}^{i-1} 。同时，要从 kk 种颜色中选出 ii 中颜色染色，而且是有顺序的，故方案数为 Aki\mathrm{A}_{k}^{i} 。 综上，总的方案数为： ans=∑i=1min⁡(n,k)Cn−1i−1Akians= \sum_{i=1}^{\min(n,k)}\mathrm{C}_{n-1}^{i-1}\mathrm{A}_{k}^{i} 可以线性求逆元，枚举 ii 实现。 时间复杂度：O(n)O(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
void init(int n) {
    inv[0]=inv[1]=1;
    for (int i=2;i<=n;i++) inv[i] = (mod-mod/i)*inv[mod%i]%mod;
for (int i = 2; i <= n; i++) inv[i] = (mod - mod / i) * inv[mod % i] % mod;
    finv[1] = f[1] = finv[0] = f[0] = 1;
    for (int i = 2; i <= n; i++) finv[i] = finv[i - 1] * inv[i] % mod;
    for (int i = 2; i <= n; i++) f[i] = f[i - 1] * i % mod;
 
}
int C(int a,int b){
	if(a==0||b==0)return 1;
	return f[a]*finv[a-b]%mod*finv[b]%mod;
}
int A(int a,int b){
	if(a==0||b==0)return 1;
	return f[a]*finv[a-b]%mod;
}
void solve(){
	
	int k;cin>>n>>k;
	init(n);
	for(int i=1;i<=n-1;i++){
		int u,v;cin>>u>>v;
	}
	int ans=0;
	for(int i=1;i<=min(n,k);i++){
		ans+=C(n-1,i-1)*A(k,i)%mod;
		ans%=mod;
	}
	cout<<ans<<endl;
}

本题如果不考虑组合数学，还可以从dp的角度考虑，我们先做一遍dfs序然后在序列上考虑。用f[i] [j] 表示树上dfs序的前i个点用了j种颜色的方法数$ f[i] [j] = f[i-1] [j] + f[i-1] [j-1] \times (k-j+1) $

  • 对于当前节点，如果选之前的颜色那么只能和父节点颜色相同，和其他点颜色相同也会必经父节点。
  • 如果不选之前的颜色，则有剩余没被选的颜色种选择

dfs序模板题

https://codeforces.com/problemset/problem/1006/E

题意：每次静态查询某个节点子树第k个被访问的点，访问顺序是以编号小的优先。

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
int l[N];
int r[N];
vector<int>e[N];
int idx=0;
int dfn[N];
int rk[N];
void dfs(int u,int fa){
	l[u]=++idx;
	dfn[u]=idx;
	rk[idx]=u;
	for(auto v:e[u]){
		if(v==fa)continue;
		dfs(v,u);
	}
	r[u]=idx;
}
void solve(){
   cin>>n>>m;
   for(int i=2;i<=n;i++){
   	int x;cin>>x;
   
   	 e[x].push_back(i);

   }
   dfs(1,0);
   for(int i=1;i<=m;i++){
   	int u,k;cin>>u>>k;
   	int len=r[u]-l[u]+1;
   	if(len<k)cout<<-1<<endl;
   	else {
   		int pos=l[u]+k-1;
   		cout<<rk[pos]<<endl;
   	}
   }
   
}

NC22494

链接：https://ac.nowcoder.com/acm/problem/22494
来源：牛客网

题面：有一棵n个节点的二叉树，1为根节点，每个节点有一个值wi。现在要选出尽量多的点。 对于任意一棵子树，都要满足： 如果选了根节点的话，在这棵子树内选的其他的点都要比根节点的值大； 如果在左子树选了一个点，在右子树中选的其他点要比它小。

题意：选的点需要满足点权值根<右<左，我们考虑dfs序按照这个偏序关系进行从而得到一个序列，所以我们只需要找到LIS,由于数据范围是1e5,所以我们需要使用单调栈加二分的方式去找到最长严格上升子序列

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
int a[N];

int lc[N],rc[N];
int ans[N];int idx=0;
void dfs(int u){
	if(u==0)return ;
	ans[++idx]=u;
	dfs(rc[u]);
	dfs(lc[u]);
}
void solve(){
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<=n;i++){
		cin>>lc[i]>>rc[i];
	}
dfs(1);
vector<int>v;
for(int i=1;i<=n;i++){
	int id=ans[i];
	v.push_back(a[id]);
}
vector<int>ls;
for(int i=0;i<(int)v.size();i++){
	//cerr<<v[i]<<endl;
	if(ls.empty()||v[i]>ls.back())ls.push_back(v[i]);
	else {
int pos=lower_bound(ls.begin(),ls.end(),v[i])-ls.begin();
	ls[pos]=v[i];
	}
}
int res=ls.size();
//res++;
cout<<res<<endl;

}

开始利用dfs序进行树上常规数据结构操作

链接：https://ac.nowcoder.com/acm/problem/204871

已知有 nn 个节点，有 n−1n-1 条边，形成一个树的结构。 给定一个根节点 kk，每个节点都有一个权值，节点i的权值为 viv_i。 给 mm 个操作，操作有两种类型：

  • 1 a x ：表示将节点 aa 的权值加上 xx
  • 2 a ：表示求 aa 节点的子树上所有节点的和（包括 aa 节点本身）

题意：进行在线的单点修改和子树点权和查询

Solution：利用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
vector<int>e[N];
int l[N],r[N];
int idx=0;
void dfs(int u,int fa){
	l[u]=++idx;
	for(auto v:e[u]){
		if(v==fa)continue;
		dfs(v,u);
	}
	r[u]=idx;
}

void solve(){
	cin>>n;
	cin>>m;
	int root;cin>>root;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<=n-1;i++){
		int u,v;cin>>u>>v;
		e[u].push_back(v);
		e[v].push_back(u);
	}
	Fenwick<int>c(n+1);
	dfs(root,0);
	for(int i=1;i<=n;i++){
		c.add(l[i],a[i]);
	}
	for(int i=1;i<=m;i++){
		int op;cin>>op;
		if(op==1){
			int id,val;
			cin>>id>>val;
			c.add(l[id],val);
		}
		else {
			int pos;cin>>pos;
			int ql=l[pos],qr=r[pos];
			int ans=c.rangeSum(ql-1,qr);
			cout<<ans<<endl;
		}
	}
}

考察离线思想的dfs序上树状数组

链接：https://ac.nowcoder.com/acm/problem/23051

华华和月月一起维护了一棵动态有根树，每个点有一个权值。刚开存档的时候，树上只有 0 号节点，权值为 0 。接下来有两种操作：

  • 操作 1：输入格式1 i1\ i，表示月月氪金使节点 i 长出了一个新的儿子节点，权值为0，编号为当前最大编号 +1（也可以理解为，当前是第几个操作 1，新节点的编号就是多少）。

  • 操作 2：输入格式 2 i a2 \ i \ a，表示华华上线做任务使节点 i 的子树中所有节点（即它和它的所有子孙节点）权值加 a 。 但是月月有时会检查华华有没有认真维护这棵树，会作出询问：

  • 询问 3：输入格式3 i3\ i，华华需要给出 i 节点此时的权值。

Solution：😊动态建树难以维护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
47
48
49
50
51
52
vector<array<int,3>>q;
//对于询问跑两遍，第一遍建树，第二遍处理修改和询问。
//对于有些点还没加进来就被处理的贡献需要记录，回答的时候减去
vector<int>e[N];
int l[N],r[N];
int idx=0;
void dfs(int u,int fa){
	l[u]=++idx;
	for(auto v:e[u]){
		if(v==fa)continue;
		dfs(v,u);
	}
	r[u]=idx;
}
void solve(){
	//由于树状数组不要0，全部点坐标+1
	a[1]=0;int cnt=1;
	cin>>m;
	for(int i=1;i<=m;i++){
		int op;cin>>op;
		if(op==1){
			int id;cin>>id;
			id++;
			e[id].push_back(++cnt);
			q.push_back({op,cnt,0});
		}
		else if(op==2){
			int u,val;cin>>u>>val;u++;
			q.push_back({op,u,val});
		}
		else {
			int pos;cin>>pos;pos++;
			q.push_back({op,pos,0});
		}
	}
	dfs(1,0);
	Fenwick<int>c(m+2);
	for(auto [x,y,z]:q){
		if(x==1)b[l[y]]=c.sum(l[y]);
		else if(x==2){
			int ql=l[y];
			int qr=r[y];
			c.add(ql,z);
			c.add(qr+1,-z);
		}
		else {
			int res=c.sum(l[y]);
			res-=b[l[y]];
			cout<<res<<endl;
		}
	}
}

Problem - 383C - Codeforces

题意：开始魔改各种操作，本题对点权的修改是子树中与自己距离是偶数的点加上权值，奇数距离需要减去，在线查询单点点权。

Solution：考虑维护两个树状数组，分别是深度是奇数和偶数的.

  • 对于修改，我们判断当前修改的点深度的奇偶性，若是奇数，则c1作为差分左端点加，右端点减。与此同时c2作与c1完全相反的操作

  • 对于查询，注意需要判断当前深度的奇偶性，它只能接受一个树状数组的贡献。

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
int l[N],r[N];
int idx=0;
int dep[N];
vector<int>e[N];
void dfs(int u,int fa){
	l[u]=++idx;
	dep[u]=dep[fa]+1;
	for(auto v:e[u]){
		if(v==fa)continue;
		dfs(v,u);
	}
	r[u]=idx;
}
void solve(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<=n-1;i++){
		int u,v;cin>>u>>v;
		e[u].push_back(v);
		e[v].push_back(u);
	}
	dfs(1,0);
	//for(int i=1;i<=n;i++)cerr<<dep[i]<<" ";
	//for(int i=1;i<=n;i++)cerr<<l[i]<<" ";
	Fenwick<int>c1(n+2),c2(n+2);
	for(int i=1;i<=m;i++){
		int op;cin>>op;
		if(op==1){
			int id,val;
			cin>>id>>val;
			//int ql=l[id],qr=r[id];
			if(dep[id]%2){
				c1.add(l[id],val);c1.add(r[id]+1,-val);
				c2.add(l[id],-val);c2.add(r[id]+1,val);
			}
			else{
				c2.add(l[id],val);c2.add(r[id]+1,-val);
				c1.add(l[id],-val);c1.add(r[id]+1,val);
			}
		}
		else {
			int id;cin>>id;
			int ql=l[id],qr=r[id];
			int ans=0;
			if(dep[id]%2)ans+=c1.rangeSum(0,ql);
			else ans+=c2.rangeSum(0,ql);
			ans+=a[id];
			cout<<ans<<endl;
		}
	}
}

Codeforces Round 316 (Div. 2) D

题意：给定一棵树，每个点的点权是个字母。每次给定查询u和h。查询某个点子树下所有深度为h的点能不能构成回文串

Solution：考虑子树问题采用dfs序相关手法。假设我们已经快速得到每次的点集，我们判断回文串的准则是最多有一个字母出现奇数次。再回过头考虑我们如何快速得到一次的点集，考虑维护深度的点集，对每一个深度开一个vector，存的是每个点的dfs序序号，每次查询的时候，我们在本次查询深度的vector里找到子树的左右边界

那么如何快速判断这些点出现次数呢？一个朴素的想法，对26个小写字母维护前缀和，但这样从时间上和空间上都不优。我们考虑只有26个小写字母，想到二进制状态压缩。进一步我们维护区间异或和，就可以字母出现次数的奇偶性，通过前缀异或和优化，这一步优化成O(1)O(1)

实现的有个常数优化细节：我们可以在dfs过程中就开始维护深度值域vector，因为dfs过程中的顺序就是我们从小到大的数。这样就省去了我们单独再把所有点分配进去，然后再全部排序。

预处理时间复杂度：O(n)O(n)

查询复杂度：O(mlog⁡(n))O(m\log(n))

debug:一开始写的就是对的，除了没发现查询本身可能根本不存在这么高的树，导致vector维护深度值域的时候开小了，re了一万年。。。

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
int n, m;
int a[N];
//考虑对每个深度创建一个vector，vector需要存下标
//通过二分dfs序找到本次需要用到的区间，预处理异或前缀和
//vector里还需要存当前的字母的状态，用压缩的二进制状态存字母存在情况‘
//利用异或可逆o1查询当前字母的配对情况，最多只能出现1个奇数情况
//才能形成回文串
int dep[N];
vector<int>e[N];
int l[N],r[N];
int idx=0;
int dfn[N];
string str=" ";
void solve(){
	cin>>n;cin>>m;
	for(int i=2;i<=n;i++){
		int x;cin>>x;
		e[x].push_back(i);
	}
	string tmp;cin>>tmp;
	str+=tmp;
	vector<vector<int>>v(n+1,vector<int>(1,0));
	vector<vector<int>>b(n+1,vector<int>(1,0));
	auto dfs=[&](auto self,int u,int fa)->void{
	l[u]=++idx;
	dfn[idx]=u;
	//cerr<<u<<" "<<idx<<endl;
	dep[u]=dep[fa]+1;
	v[dep[u]].push_back(l[u]);
	for(auto v:e[u]){
		if(v==fa)continue;
		self(self,v,u);
	}
	r[u]=idx;
};
	dfs(dfs,1,0);
	
	int mxh=*max_element(dep,dep+n+1);
	
	
	for(int i=1;i<=mxh;i++){
		for(int j=1;j<(int)v[i].size();j++){
			int pos=v[i][j];
			int id=dfn[pos];
	//cerr<<i<<" "<<v[i][j].first<<" "<<v[i][j].second<<endl;
	int num=1<<(str[id]-'a');
			b[i].push_back({num^(b[i].back())});
	   }
	}
	//cerr<<"query"<<endl;
	for(int i=1;i<=m;i++){
		int pos,h;cin>>pos>>h;
		int ql=l[pos],qr=r[pos];
		
		auto &vt=v[h];
		auto &bt=b[h];
	int ansl=lower_bound(vt.begin(),vt.end(),ql)-vt.begin();
	int ansr=upper_bound(vt.begin(),vt.end(),qr)-vt.begin();
		ansr-=1;
		//判空串
		if(ql==qr){
			cout<<"Yes"<<endl;
			continue ;
		}
		if(ansr<=ansl){
			cout<<"Yes"<<endl;
			continue ;
		}
		//cerr<<i<<" "<<ql<<" "<<qr<<endl;
		//cerr<<i<<" "<<ansl<<" "<<ansr<<endl;
		int res=bt[ansr]^bt[ansl-1];
		if(__builtin_popcount(res)<=1)cout<<"Yes"<<endl;
		else cout<<"No"<<endl;
	}
}

Codeforces Round 130 (Div. 2)E

本题：是上一题的基础版，哎哎，做题拓扑序不对。。题意：给出一个森林。每次查询一个点的k级表亲数量。(k级表亲：就是k级祖先的儿子，并且和你同一深度的儿子)

Solution：首先利用倍增父节点数组，花费O(log⁡n)O(\log n)的时间找到k级祖先，然后我们和上题一样维护每个点dfs序的管辖范围，再维护值域高度的dfs序，利用左右边界二分找到k级表亲

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
int n, m;
vector<int>h[N];
struct edge{
    int v,w;
};
//思考：要想知道一个数有几个二级制位，直接n=__lg(x)
//我们可以知道<n最近的2的次幂，9最大的是8，8虽然是2的3次方，但要遍历它的每一位
//需要3到0开始，也就是考虑到0的影响，我们可以正好满足偏移。
//2的3次方有四位，也就是__lg(x)就是我们需要的最高位，从它开始往低遍历
vector<edge>e[N];
int dep[N];
int d[N];
const int len=__lg(N);
int f[N][len+2];
int l[N],idx=0;int r[N];
int ans=0;

void dfs(int u,int fa){
    dep[u]=dep[fa]+1;
     l[u]=++idx;
 h[dep[u]].push_back(l[u]);
    f[u][0]=fa;
    l[u]=++idx;
    for(int i=1;i<=len;i++)f[u][i]=f[f[u][i-1]][i-1];
    //预处理倍增数组

    for(auto [v,w]:e[u]){
        if(v==fa)continue;
        d[v]=d[u]+w;
        dfs(v,u);
    }
    r[u]=idx;
}


void solve(){
	cin>>n;
	vector<int>root;
	for(int i=1;i<=n;i++){
		int x;cin>>x;
		if(x==0)root.push_back(i);
		else e[x].push_back({i,1});
	}
	for(auto x:root){
		//cerr<<x<<endl;
		dfs(x,0);
	}
//	for(int i=1;i<=n;i++)cerr<<dep[i]<<" ";
	cin>>m;
	for(int i=1;i<=m;i++){
		int pos,k;cin>>pos>>k;
		int dp=dep[pos];
		if(dep[pos]<=k){
			cout<<0<<" ";continue;
		}
		int ed=dep[pos]-k;
		for(int i=len;i>=0;i--){
        if(dep[f[pos][i]]>=ed)pos=f[pos][i];
    }
    auto &tmp=h[dp];
    int ql=l[pos],qr=r[pos];
    int ansl=lower_bound(tmp.begin(),tmp.end(),ql)-tmp.begin();
    int ansr=upper_bound(tmp.begin(),tmp.end(),qr)-tmp.begin()-1;
    // if(ansr<ansl){
    	// cout<<0<<endl;
    // }
    int ans=ansr-ansl;
    cout<<ans<<" ";
	}
}

Colorful Tree (nowcoder.com)

题意：一棵树，每个点有自己的颜色。多次查询修改

  • 修改：将一个点颜色改成另一种颜色
  • 查询：查询某种颜色的点最小连通子图的边数

Solution：破解点是手动模拟。从简单到难考虑，先考虑两个点，再考虑加入一个点的贡献，从2到3很麻烦，需要分类讨论，但有可能整个题目关键就在于此。为下面整个流程提前总结

  1. 动态维护每个颜色的点集对应的dfs序集合，修改时要对当前贡献删除，对新加贡献增加，所处位置也是动态的只能在线算
  2. 实现方面利用树链剖分求lca，dfs序也在dfs1里面解决。剩下的就是实现ADD和del函数，分别对边界和中间情况讨论处理。

题目： — 给一棵无根树。每个点有一个颜色cic_i。mm个操作。

  • U xk ykU\space x_k \space y_k：将结点xkx_k的颜色修改为yky_k；

  • Q ykQ\space y_k：问所有颜色为yky_k的结点的生成树大小。(若不存在颜色为yky_k的结点输出−1-1) n、m、ci≤1e5n、m、c_i≤1e5

  • 做法：可以用dfsdfs序来维护相同颜色结点的生成树。 考虑若颜色cc的只有22个结点uu、vv，则其生成树大小就是两个结点在原树上的距离，记为dis(u,v)dis(u,v)。此时，如果加入第33个结点xx，xx对生成树的贡献能用树上距离算出来： ①若xx在uu、vv之间：（有如下2种情况） xx不在u，vu，v路径上和xx在u，vu，v路径上。 图片说明 ②若xx不在uu、vv之间：（有如下2种情况） 图片说明 以上所有情况xx对生成树的贡献都是d=(dis(u,x)+dis(x,v)−dis(u,v))/2d = (dis(u,x)+dis(x,v)-dis(u,v))/2

  • 所以我们可以对相同颜色点的集合按dfsdfs序排序维护（用setset）。每次加点或删点就取出左右相邻的22个点计算贡献，若不存在左或右相邻，就用第②种情况，在一边取22个点计算贡献，式子都是一样的。 至于dis(u，v)dis(u，v)的计算。以11为根算出每个点的深度dep[i]dep[i]。dis(u,v)=dep[u]+dep[v]−2∗dep[lca(u,v)]dis(u,v)=dep[u]+dep[v]-2*dep[lca(u,v)]。(lcalca最近公共祖先)

debug:由于没有封装函数导致写了两百行不想调了，遂先放一份大佬的代码

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
#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;

int head[N], to[N << 1], nex[N << 1], cnt = 1;

int son[N], dep[N], fa[N], sz[N], rk[N], id[N], top[N], tot;

int n, m, value[N], ans[N];

void Add(int x, int y) {
    to[cnt] = y;
    nex[cnt] = head[x];
    head[x] = cnt++;
}

void dfs1(int rt, int f) {
    dep[rt] = dep[f] + 1;
    sz[rt] = 1, rk[++tot] = rt, id[rt] = tot;
    fa[rt] = f;
    for(int i = head[rt]; i; i = nex[i]) {
        if(to[i] == f) continue;
        dfs1(to[i], rt);
        sz[rt] += sz[to[i]];
        if(!son[rt] || sz[to[i]] > sz[son[rt]]) son[rt] = to[i];
    }
}

void dfs2(int rt, int tp) {
    top[rt] = tp;
    if(!son[rt]) return ;
    dfs2(son[rt], tp);
    for(int i = head[rt]; i; i = nex[i]) {
        if(to[i] == fa[rt] || to[i] == son[rt]) continue;
        dfs2(to[i], to[i]);
    }
}

int lca(int x, int y) {
    while(top[x] != top[y]) {
        if(dep[top[x]] < dep[top[y]]) swap(x, y);
        x = fa[top[x]];
    }
    return dep[x] < dep[y] ? x : y;
}

int dis(int x, int y) {
    x = rk[x], y = rk[y];
    return dep[x] + dep[y] - 2 * dep[lca(x, y)];
}

set<int> st[N];

void add(int x, int value) {
    if(st[value].size() == 0) {
        ans[value] = 0;
        st[value].insert(x);
        return ;
    }
    auto it = st[value].lower_bound(x);
    if(it == st[value].begin() || it == st[value].end()) {
        auto y = st[value].begin();
        auto z = st[value].rbegin();
        ans[value] += (dis(x, *y) + dis(x, *z) - dis(*y, *z)) >> 1;
    }
    else {
        auto y = it, z = it;
        y--;
        ans[value] += (dis(x, *y)+dis(x, *z)-dis(*y, *z))/2;
    }
    st[value].insert(x);
}

void del(int x, int value) {
    if (st[value].size() == 1){
        st[value].erase(x); ans[value] = -1;
        return;
    }
    st[value].erase(x);
    auto it = st[value].lower_bound(x);
    if (it == st[value].begin() || it == st[value].end()){
        auto y = st[value].begin();
        auto z = st[value].rbegin();
        ans[value] -= (dis(x, *y)+dis(x, *z)-dis(*y, *z))/2;
    }else{
        auto y = it, z = it; y--;
        ans[value] -= (dis(x, *y)+dis(x, *z)-dis(*y, *z))/2;
    }
}

int main() {
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    // ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    scanf("%d", &n);
    for(int i = 1; i < n; i++) {
        int x, y;
        scanf("%d %d", &x, &y);
        Add(x, y);
        Add(y, x);
    }
    dfs1(1, 0);
    dfs2(1, 1);
    memset(ans, -1, sizeof ans);
    for(int i = 1; i <= n; i++) {
        scanf("%d", &value[i]);
        add(id[i], value[i]);
    }
    scanf("%d", &m);
    for(int i = 1; i <= m; i++) {
        char op;
        cin >> op;
        if(op == 'Q') {
            int value;
            scanf("%d", &value);
            printf("%d\n", ans[value]);
        }
        else {
            int x, color;
            scanf("%d %d", &x, &color);
            del(id[x], value[x]);
            value[x] = color;
            add(id[x], value[x]);
        }
    }
    return 0;
}

​

Alliances https://ac.nowcoder.com/acm/problem/13950

题意：给出一棵树，每次询问一个点集，求包含这个点集的最小生成树与询问点x的最短距离，要求每次询问的复杂度控制在O(nlogn)O(nlogn)之内。

Solution：对于一个点集需要先找出他们的共同lca，以这个为基础再进行讨论

在每个询问中

LCALCA为在这次询问中所涉及的所有被占据结点的LCALCA，VV为首都位置

  • VV不是LCALCA的子孙，此时答案为VV到LCALCA的距离

  • VV是LCALCA的子孙。 对于第二种有必要再一次进行分类：

    • 点VV为被占领的点之一，此时答案为00。

    • 点VV不为被占领的点，且点VV到LCALCA的路径上存在点u!=LCAu!=LCA并且uu被占领，此时答案为V到最近的这样的点u的距离。

  • 点VV到LCA的路径上没有被控制的点，此时答案为LCALCA到VV的距离。

对答案思考清楚后，下面考虑如何实现

首先LCA是可以快速求得的,对于第二种的三小种情况，看起来难以下手。其实我们只要画图就会发现，我们只需要对每一个联盟的排序后的点击二分(V的dfs序所处位置)，然后位置左右的对应的点t1,t2到LCA的路径已经被控制，我们只需要求tit_{i}和V的lca.

答案就是答案就是$\min_\ {{dis(lca(t_{i},v),v)}}$

代码总结：

  • 对于联盟的信息我们需要先存起来，在询问的时候对涉及的每个联盟进行dfs序二分，计算更新答案。对于二分边界需要特别处理。
  • lca采用树链剖分求得，dfs序在过程中也得到

debug：重大坏习惯：多重循环的时候只用i一个变量

多重循环的时候一定不要写快了就放松警惕了。

对于这种变量名较多的时候，写的时候就注意含义，数组的含义是什么要想清楚，当前定义的变量是点的编号，还是dfs序，还是联盟编号？
整理md格式

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
int n, m;
int a[N];
vector<int> e[N];
vector<int>g[N];
int fa[N],son[N],dep[N],siz[N];
int top[N];
int high[N];
int l[N],r[N],idx=0;
int dfn[N];
void dfs1(int u,int f){ //搞fa,dep,son
  fa[u]=f;siz[u]=1;dep[u]=dep[f]+1;
  l[u]=++idx;
  dfn[idx]=u;
  for(int v:e[u]){
    if(v==f) continue;
    dfs1(v,u);
    siz[u]+=siz[v];
    if(siz[son[u]]<siz[v])son[u]=v;
  }
  r[u]=idx;
}
void dfs2(int u,int t){ //搞top
  top[u]=t;  //记录链头
  if(!son[u]) return; //无重儿子
  dfs2(son[u],t);     //搜重儿子
  for(int v:e[u]){
    if(v==fa[u]||v==son[u])continue;
    dfs2(v,v); //搜轻儿子
  }
}
int lca(int u,int v){
  while(top[u]!=top[v]){
    if(dep[top[u]]<dep[top[v]])swap(u,v);
    u=fa[top[u]];
  }
  return dep[u]<dep[v]?u:v;
}
int dis(int u,int v){
	return dep[u]+dep[v]-2*dep[lca(u,v)];
}


void solve(){
	cin>>n;
 for(int i=1;i<=n-1;i++){
 	int u,v;cin>>u>>v;
 	e[u].push_back(v);
 	e[v].push_back(u);
 }
  dfs1(1,0);
  dfs2(1,1);
  //for(int i=1;i<=n;i++)cerr<<l[i]<<" ";
    cin>>m;
  for(int i=1;i<=m;i++){
  	int num;cin>>num;
  	for(int j=1;j<=num;j++){
  		int x;cin>>x;
  		if(high[i])high[i]=lca(high[i],x);
  		else high[i]=x;
  		g[i].push_back(l[x]);
  	}
  	sort(g[i].begin(),g[i].end());
  
  	//for(auto x:g[i])cerr<<x<<" ";
  //cerr<<endl;
  }
  
  int q;cin>>q;
  for(int i=1;i<=q;i++){
  	int rt,num;cin>>rt>>num;
  	int cr=0;
  //	cerr<<rt<<" "<<num<<endl;
  	for(int j=1;j<=num;j++){
  		cin>>a[j];
  		int id=a[j];
  		if(cr)cr=lca(cr,high[id]);
  		else cr=high[id];
  		
  	}
  	int pos=l[rt];
  	//cerr<<rt<<" "<<cr<<endl;
  	if(l[cr]>pos||r[cr]<pos){
  		cout<<dis(cr,rt)<<endl;
  		continue ;
  	}
  	int ans=inf;
  	
  //	cerr<<rt<<" "<<cr<<endl;
  	for(int j=1;j<=num;j++){
  		int id=a[j];
  	//a是联盟编号，g中存的编号中的点对应的dfs序，dfn是根据dfs序找回点的编码
  		auto ql=lower_bound(g[id].begin(),g[id].end(),pos);
  		if(ql==g[id].begin()){
  			ans=min(ans,dis(rt,lca(rt,dfn[*ql])));
  		}
  		else if(ql==g[id].end()){
  				
  		ql--;
  			ans=min(ans,dis(rt,lca(rt,dfn[*ql])));
  		}
  		else {
  			ans=min(ans,dis(rt,lca(rt,dfn[*ql])));
  			ql--;
  			ans=min(ans,dis(rt,lca(rt,dfn[*ql])));
  		}
  		
  	}
  	cout<<ans<<endl;
  }
}