A. 苹果树2

  • 用线段树去维护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
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    #include<bits/stdc++.h>
    #define M 200001
    using namespace std;
    int n,m,tot;
    int A[M],to[M];
    int L[M],R[M];
    vector<int>Q[M];
    class {
    	public:
    		int l,r,v;
    } tree[M<<2];
    void dfs(int x,int q) {
    	L[x]=++tot,to[tot]=x;
    	for(int i=0; i<Q[x].size(); ++i) {
    		int y=Q[x][i];
    		if(y==q)continue;
    		dfs(y,x);
    	}
    	R[x]=tot;
    }
    int Max(int a,int b) {
    	if(A[a]>A[b])return a;
    	if(A[b]>A[a])return b;
    	if(a<b)return a;
    	return b;
    }
    int build(int L,int R,int p) {
    	tree[p].l=L,tree[p].r=R;
    	if(L==R)return tree[p].v=to[L];
    	int mid=L+R>>1;
    	return tree[p].v=Max(build(L,mid,p<<1),build(mid+1,R,p<<1|1));
    }
    void Up(int x,int p) {
    	if(tree[p].l==tree[p].r)return;
    	int mid=tree[p].l+tree[p].r>>1;
    	if(x<=mid)Up(x,p<<1);
    	else Up(x,p<<1|1);
    	tree[p].v=Max(tree[p<<1].v,tree[p<<1|1].v);
    }
    int query(int L,int R,int p) {
    //	printf("tree[p].l=%d tree[p].r=%d p=%d\n",tree[p].l,tree[p].r,p);
    	if(tree[p].l==L&&tree[p].r==R)return tree[p].v;
    	int mid=tree[p].l+tree[p].r>>1;
    	if(R<=mid)return query(L,R,p<<1);
    	if(L>mid)return query(L,R,p<<1|1);
    	return Max(query(L,mid,p<<1),query(mid+1,R,p<<1|1));
    }
    int main() {
    	scanf("%d%d",&n,&m);
    	for(int i=1; i<=n; ++i)
    		scanf("%d",&A[i]);
    	for(int i=1; i<n; ++i) {
    		int u,v;
    		scanf("%d%d",&u,&v);
    		Q[u].push_back(v);
    		Q[v].push_back(u);
    	}
    	dfs(1,0);
    	build(1,n,1);
    	for(int i=1; i<=m; ++i) {
    		int c,x,y;
    		scanf("%d%d",&c,&x);
    		if(c<2) {
    			printf("%d\n",y=query(L[x],R[x],1));
    			A[y]=0;
    			Up(L[y],1);
    		} else {
    			scanf("%d",&y);
    			A[x]+=y;
    			Up(L[x],1);
    		}
    	}
    	return 0;
    }

B. LCA查询

双指针算最大LCA

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
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,m,dep[N],dfn[N],f[N][21];
int a[N],b[N],la,lb,tot;
vector<int> G[N];
void dfs(int u,int fa){
	dfn[u]=++tot;
	dep[u]=dep[fa]+1;
	f[u][0]=fa;
	for(int j=1;j<=19;j++) f[u][j]=f[f[u][j-1]][j-1];
	for(auto v:G[u])
		if(v!=fa) dfs(v,u);
}
int lca(int x,int y){
	if(dep[x]>dep[y]) swap(x,y);
	for(int i=19;i>=0;i--)
		if(dep[f[y][i]]>=dep[x]) y=f[y][i];
	if(x==y) return x;
	for(int i=19;i>=0;i--)
		if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
	return f[x][0];
}
bool cmp(int x,int y){
	return dfn[x]<dfn[y];
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n>>m;
	for(int i=1,u,v;i<n;i++){
		cin>>u>>v;
		G[u].push_back(v);
		G[v].push_back(u);
	}
	dfs(1,0);
	while(m--){
		cin>>la;
		for(int i=1;i<=la;i++) cin>>a[i];
		cin>>lb;
		for(int i=1;i<=lb;i++) cin>>b[i];
		sort(a+1,a+la+1,cmp);
		sort(b+1,b+lb+1,cmp);
		int j=1,ans=1;
		for(int i=1;i<=la;i++){
			while(j<=lb&&dfn[b[j]]<dfn[a[i]]) j++;
			if(j>1) ans=max(ans,dep[lca(a[i],b[j-1])]);
			if(j<=lb) ans=max(ans,dep[lca(a[i],b[j])]);
		}
		cout<<ans<<'\n';
	}
	return 0;
}