lca专题二

自用笔记算法

lca专题二

HDU 5293

题目要求

给你一棵树，树上有n个点。
然后给你m条链，每条链都有权值，然后让你选择一些不相交的链，使得权值和最大。

参考AC代码

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
#include<bits/stdc++.h>
#define maxn 100050
#define mm(a,b) memset(a,b,sizeof(a))
using namespace std;
struct node{
	int l,r,w;
	node(int l,int r,int w):l(l),r(r),w(w){}
};
int t,n,m,step;
int tree[maxn<<2];
int sz[maxn],fa[maxn],son[maxn],dep[maxn];
int top[maxn],in[maxn],out[maxn];
int sum[maxn],dp[maxn];
vector<int>e[maxn];
vector<node>q[maxn];
void init(){
	for(int i=0;i<=n;i++) e[i].clear(),q[i].clear();
    mm(sz,0),mm(dep,0),mm(fa,0),mm(son,0);
    mm(in,0),mm(top,0),mm(out,0);
    mm(sum,0),mm(dp,0),mm(tree,0);
    step=0;
}
void add(int x,int val){
    while(x<=n) {
        tree[x]+=val;
        x+=x&(-x);
    }
}
int get(int x){
    int res=0;
    while (x){
        res+=tree[x];
        x-=x&(-x);
    }
    return res;
}
void dfs1(int x,int f,int deep){
    sz[x]=1,fa[x]=f,son[x]=0,dep[x]=deep;
    int len=e[x].size();
    for(int i=0;i<len;i++){
        int next=e[x][i];
        if(next==f) continue;
        dfs1(next,x,deep+1);
        sz[x]+=sz[next];
        if(sz[son[x]]<sz[next]) son[x]=next;
    }
}
void dfs2(int x,int tp){
    top[x]=tp;
    in[x]=++step;
    if(son[x]) dfs2(son[x],tp);
    int len=e[x].size();
    for(int i=0;i<len;i++){
        int next=e[x][i];
        if(next==fa[x] || next==son[x]) continue;
        dfs2(next,next);
    }
    out[x]=step;
} 
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]];
    }
    if(dep[u]>dep[v]) swap(u,v);
    return u;
}
void dfs(int x,int fa){
	for(int i=0;i<e[x].size();i++){
		int next=e[x][i];
		if(next==fa) continue;
		dfs(next,x);
		sum[x]+=dp[next];
	}
	dp[x]=sum[x];
	for(int i=0;i<q[x].size();i++){
		int l=q[x][i].l;
		int r=q[x][i].r;
		int w=q[x][i].w;
		dp[x]=max(dp[x],sum[x]+w+get(in[l])+get(in[r]));
	}
	add(in[x],sum[x]-dp[x]);
	add(out[x]+1,dp[x]-sum[x]);
}
int main(){
//	freopen("input.txt","r",stdin);
	scanf("%d",&t);
	while(t--){
		scanf("%d%d",&n,&m);
		init();
		for(int i=1;i<n;i++){
			int u,v;
			scanf("%d%d",&u,&v);
			e[u].push_back(v);
			e[v].push_back(u);
		}
		dfs1(1,0,0);
		dfs2(1,1);
		for(int i=1;i<=m;i++){
			int u,v,w;
			scanf("%d%d%d",&u,&v,&w);
			q[lca(u,v)].push_back(node(u,v,w));
		}
		dfs(1,0);
		printf("%d\n",dp[1]);
	}
	return 0;
}

思路

lca+树形dp+树状数组
要求权值最大，按照树形dp的思路去考虑，用dp[i]表示以第i个点为根节点的子树的最优解。
dp[i]的状态转移公式,有两种可能,第一种：第i个节点上不出现链，那么dp[i]=∑(dp[k] | k为i的子节点)；
第二种：第i个节点上出现链，如果选择加入这条链，那么dp[i]=w(链的权值)+∑(dp[k] | k为链上的节点的子节点)=w+∑(sum[k] | k为链上的节点 )-∑(dp[k] | k为链上的节点)
sum[i]表示i节点的所有子节点的dp和，在 ∑(sum[k] | k为链上的节点 ) - ∑(dp[k] | k为链上的节点) 中减去的dp[k]会由它的父节点的sum补全。这样就得到了状态转移公式。
所减去的地方：sum[k] - dp[k]用树状数组维护
注意dfs序区间的开闭问题：out[x]+1

HDU 5296

题目要求

一棵树 n个点 有边权 q次操作
1 x：把点x加入到集合s中(若点x不在集合中)
2 x：把点x移除集合s(若点x在集合中)
对于每次询问 输出为了使集合S中所有的点联通需要最少的边权

参考AC代码

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
#include<bits/stdc++.h>
#define maxn 100050
#define mm(a,b) memset(a,b,sizeof(a))
using namespace std;
struct node{
	int to,w;
	node(int to,int w):to(to),w(w){}
};
int t,n,q,step;
vector<node>e[maxn];
set<int>st;
int sz[maxn],dep[maxn],fa[maxn],son[maxn];
int in[maxn],top[maxn],val[maxn],dis[maxn];
int vis[maxn];
void init(){
	for(int i=0;i<=n;i++) e[i].clear();
	st.clear();
    mm(sz,0),mm(dep,0),mm(fa,0),mm(son,0);
    mm(in,0),mm(top,0),mm(val,0),mm(vis,0),mm(dis,0);
    step=0;
}
void dfs1(int x,int f,int deep){
    sz[x]=1,fa[x]=f,son[x]=0,dep[x]=deep;
    int len=e[x].size();
    for(int i=0;i<len;i++){
        int next=e[x][i].to,ww=e[x][i].w;
        if(next==f) continue;
        dis[next]=dis[x]+ww;
        dfs1(next,x,deep+1);
        sz[x]+=sz[next];
        if(sz[son[x]]<sz[next]) son[x]=next;
    }
}
void dfs2(int x,int tp){
    top[x]=tp;
    in[x]=++step;
    val[step]=x; 
    if(son[x]) dfs2(son[x],tp);
    int len=e[x].size();
    for(int i=0;i<len;i++){
        int next=e[x][i].to;
        if(next==fa[x] || next==son[x]) continue;
        dfs2(next,next);
    }
} 
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]];
    }
    if(dep[u]>dep[v]) swap(u,v);
    return u;
}
int solve(int x){
	if(st.size()==0) return 0;
	set<int>::iterator pos=st.upper_bound(in[x]);
	int a,b;
	if(pos==st.begin() || pos==st.end()){
		a=val[*st.rbegin()];
		b=val[*st.begin()];
	}
	else{
		a=val[*pos];
		pos--;
		b=val[*pos];
	}
	return dis[x]+dis[lca(a,b)]-dis[lca(x,a)]-dis[lca(x,b)];
}
int Case=1;
int main(){
//	freopen("input.txt","r",stdin);
	scanf("%d",&t);
	while(t--){
		printf("Case #%d:\n",Case++);
		scanf("%d%d",&n,&q);
		init();
		for(int i=1;i<n;i++){
			int u,v,w;
			scanf("%d%d%d",&u,&v,&w);
			e[u].push_back(node(v,w));
			e[v].push_back(node(u,w));
		}
		dfs1(1,0,0);
		dfs2(1,1);
		int ans=0;
		while(q--){
			int op,x;
			scanf("%d%d",&op,&x);
			if(op==1 && !vis[in[x]]){
				ans+=solve(x);
				vis[in[x]]=1;
				st.insert(in[x]);
			}
			else if(op==2 && vis[in[x]]){
				st.erase(in[x]);
				vis[in[x]]=0;
				ans-=solve(x);
			}
			printf("%d\n",ans);
		}
	}
	return 0;
}

思路

lca+dfs序
对于添加或者删除一个点造成的影响有公式：dis[x]+dis[lca(a,b)]-dis[lca(x,a)]-dis[lca(x,b)]
a是dfs序大于x的点 b是dfs序小于x的点 若ab不同时存在 找到字典序最大和最小的点a和b即可
公式画图即可理解
寻找大于x和小于x的dfs序的点用set存dfs序后二分查找
注意添加和删除中ans更新的顺序
额外补充：
c.begin() 返回一个迭代器，它指向容器c的第一个元素
c.end() 返回一个迭代器，它指向容器c的最后一个元素的下一个位置
c.rbegin() 返回一个逆序迭代器，它指向容器c的最后一个元素
c.rend() 返回一个逆序迭代器，它指向容器c的第一个元素前面的位置

cf gym 100015

题目要求

n点n边 无向图 正边权
问任意两点的最短距离

参考AC代码

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
#include<bits/stdc++.h>
#define maxn 100050
#define mm(a,b) memset(a,b,sizeof(a))
using namespace std;
struct node{
	int to,w;
	node(int to,int w):to(to),w(w){}
};
int n,q;
int uu,vv,ww;
vector<node>e[maxn];
int deep[maxn],f[maxn],anc[maxn][25];
int p[maxn],dis[maxn];
void init(){
	for(int i=0;i<=n;i++) e[i].clear();
	for(int i=0;i<=n;i++) p[i]=i;
	mm(f,0),mm(anc,0),mm(deep,0),mm(dis,0);
	deep[1]=1;
}
int find(int x){
	return x==p[x]?x:p[x]=find(p[x]);
}
void merge(int u,int v){
	int x=find(u);
	int y=find(v);
	if(x!=y) p[x]=y;
}
void dfs(int x,int fa){
    anc[x][0]=f[x];
    for(int i=1;i<=20;i++) anc[x][i]=anc[anc[x][i-1]][i-1];
    for(int i=0;i<e[x].size();i++){
        int next=e[x][i].to,weight=e[x][i].w;
        if(next!=fa){
            f[next]=x;
            deep[next]=deep[x]+1;
            dis[next]=dis[x]+weight;
            dfs(next,x);
        }
    }
}
int lca(int x,int y){
    if(deep[x]<deep[y]) swap(x,y);
    for(int i=20;i>=0;i--) if(deep[anc[x][i]]>=deep[y]) x=anc[x][i];
    if(x==y) return x;
    for(int i=20;i>=0;i--) if(anc[x][i]!=anc[y][i]) x=anc[x][i],y=anc[y][i];
    return f[x];
}
int get(int u,int v){
	int fa=lca(u,v);
	return dis[u]+dis[v]-2*dis[fa];
}
int main(){
//	freopen("input.txt","r",stdin);
	while(scanf("%d",&n)!=EOF){
		if(n==0) break;
		init();
		for(int i=1;i<=n;i++){
			int u,v,w;
			scanf("%d%d%d",&u,&v,&w);
			u++,v++;
			if(find(u)==find(v)){
				uu=u,vv=v,ww=w;
				continue;
			}
			merge(u,v);
			e[u].push_back(node(v,w));
			e[v].push_back(node(u,w));
		}
		dfs(1,0);
		scanf("%d",&q);
		while(q--){
			int u,v;
			scanf("%d%d",&u,&v);
			u++,v++;
			int ans=get(u,v);
			ans=min(ans,get(u,uu)+ww+get(vv,v));
			ans=min(ans,get(u,vv)+ww+get(uu,v));
			printf("%d\n",ans);
		}
	}
	return 0;
}

思路

随便找一个环，然后在这个环上随便去掉一条边，然后就比较这个树上的距离小，还是经过这条边的饿距离小 一共就三条路径
比如你去掉的边是a,b,边权是w，你查询u,v
那么你比较dis(u,v),dis(u,a)+w+dis(b,v),dis(u,b)+w+dis(a,u)就好了
找环上的边，用并查集

cdoj 92

题目要求

给你一棵树，有边权，然后加了一条边，给Q次询问，问你这些点之间的最短距离缩短了多少
缩短为负输出0

思路

和上题类似 只需要询问部分改成

1
2
3
4
int x1=get(u,v);
int x2=get(u,uu)+ww+get(vv,v);
int x3=get(u,vv)+ww+get(uu,v);
int ans=max(x1-min(x2,x3),0);

cf 575b

题目要求

在一棵树上，有一些边是单向边，有一些是双向边。如果逆向行驶单向边，第一次逆行这条边，罚款1，……第i次罚款2^i.
然后给出k个点，分别为ki,到达ki后再去ki+1，初始的时候在1点。问按照上面的安排，最少被罚多少。mod10^9+7

参考AC代码

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
#include<bits/stdc++.h>
#define maxn 100050
#define LL long long
#define mm(a,b) memset(a,b,sizeof(a))
using namespace std;
const int mod=1e9+7;
LL qpow(LL x,LL y){LL re=1,base=x%mod;while(y){if(y&1)re=(re*base)%mod;base=(base*base)%mod;y>>=1;}return re;}
struct node{
	int to,w;
	node(int to,int w):to(to),w(w){}
};
int n,k;
vector<node>e[maxn];
int deep[maxn],f[maxn],anc[maxn][25];
int up[maxn],cnt[2][maxn];
void init(){
	for(int i=0;i<=n;i++) e[i].clear();
	mm(f,0),mm(anc,0),mm(deep,0);
	mm(up,0),mm(cnt,0);
	deep[1]=1;
}
void dfs1(int x,int fa){
    anc[x][0]=f[x];
    for(int i=1;i<=20;i++) anc[x][i]=anc[anc[x][i-1]][i-1];
    for(int i=0;i<e[x].size();i++){
        int next=e[x][i].to;
        if(next!=fa){
            f[next]=x;
            deep[next]=deep[x]+1;
            up[next]=-e[x][i].w;
            dfs1(next,x);
        }
    }
}
int lca(int x,int y){
    if(deep[x]<deep[y]) swap(x,y);
    for(int i=20;i>=0;i--) if(deep[anc[x][i]]>=deep[y]) x=anc[x][i];
    if(x==y) return x;
    for(int i=20;i>=0;i--) if(anc[x][i]!=anc[y][i]) x=anc[x][i],y=anc[y][i];
    return f[x];
}
void dfs2(int x){
	for(int i=0;i<e[x].size();i++){
		int next=e[x][i].to;
		if(next==anc[x][0]) continue;
		dfs2(next);
		for(int j=0;j<2;j++) cnt[j][x]+=cnt[j][next];
	}
}
int main(){
	freopen("input.txt","r",stdin);
	scanf("%d",&n);
	init();
	for(int i=1;i<n;i++){
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		if(w==0){
			e[u].push_back(node(v,0));
			e[v].push_back(node(u,0));
		}
		else{
			e[u].push_back(node(v,1));
			e[v].push_back(node(u,-1));
		}
	}
	dfs1(1,0);
	scanf("%d",&k);
	int pre=1,now;
	while(k--){
		scanf("%d",&now);
		if(pre==now) continue;
		int x=lca(pre,now);
		cnt[0][pre]++;
		cnt[0][x]--;
		cnt[1][now]++;
		cnt[1][x]--;
		pre=now;
	}
	dfs2(1);
	int ans=0;
	for(int i=1;i<=n;i++){
		if(!up[i]) continue;
		if(up[i]==-1) ans=(ans+qpow(2,cnt[0][i])-1)%mod;
		else ans=(ans+qpow(2,cnt[1][i])-1)%mod;
	}
	ans=(ans+mod)%mod;
	printf("%d\n",ans);
	return 0;
}

思路

本题实质是记录每条路径反向经过的次数 然后快速幂统计答案
通过权值0 1 -1的赋值和up数组的对反 最后实现的结果是：
双向边依旧为0 单向边如果路径朝上 w=1 如果朝下 w=-1
cnt[0][]记录的是朝上的路径 cnt[1][]记录的是朝下的路径
最后等价于up=-1的点统计cnt[0][i]的路径条数 up=0的点统计cnt[1][i]的路径条数
从a->b，可以拆分成a->lca(a,b)+lca(a,b)->b，每次a++，lca(a,b)– b++，lca(a,b)–
dfs2统计计算出所有结点下(相当于统计每条边的贡献)的cnt[0][]和cnt[1][] 若up[i]不等于0 快速幂更新答案

本文标题:lca专题二

文章作者:Hippopmonkey

发布时间:2017-10-01, 15:00:14

最后更新:2017-10-02, 14:59:17

原始链接:http://xuboming8.github.io/2017/10/01/lca专题二/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. lca专题二
    1. 1.1. HDU 5293
      1. 1.1.1. 题目要求
      2. 1.1.2. 参考AC代码
      3. 1.1.3. 思路
    2. 1.2. HDU 5296
      1. 1.2.1. 题目要求
      2. 1.2.2. 参考AC代码
      3. 1.2.3. 思路
    3. 1.3. cf gym 100015
      1. 1.3.1. 题目要求
      2. 1.3.2. 参考AC代码
      3. 1.3.3. 思路
    4. 1.4. cdoj 92
      1. 1.4.1. 题目要求
      2. 1.4.2. 思路
    5. 1.5. cf 575b
      1. 1.5.1. 题目要求
      2. 1.5.2. 参考AC代码
      3. 1.5.3. 思路
|