八段第一课树结构升级总结

A 间隔选点-树上版本

解法

设 $f_{i,0/1}$ 表示当前是编号为为 $i$ 的点，是否有选。

然后当前节点选的状态就可以加上所有儿子不选的状态，而当前节点不选的状态则可以加上儿子选与不选的状态。

所以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
#include <bits/stdc++.h>
using namespace std;

const int N = 20000;

int a[N],h[N],e[N],ne[N],idx;
int f[N][2];
int n;
void add(int x,int y)
{
    e[idx]=y,ne[idx]=h[x],h[x]=idx++;
}
void dfs(int u,int fa)
{
    f[u][0]=0,f[u][1]=a[u];
    for(int i=h[u];i!=-1;i=ne[i])
    {
        if(e[i]!=fa) dfs(e[i],u),f[u][0]+=max(f[e[i]][0],f[e[i]][1]),f[u][1]+=max(f[e[i]][0],0);
    }
}
int main()
{
    memset(h,-1,sizeof h);
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=n-1;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y);add(y,x);
    }
    dfs(1,0);
    printf("%d",max(f[1][0],f[1][1]));
}

B 苹果树

解法

我们可以设 $f_{i,j,0/1}$ 表示当前停留在 $i$ 点，使用 $j$ 步 回/不回 到原点的最大价值。

那么对于一个点分三种情况。

  1. 走到儿子 $y$ 然后回来，那么可以由 $f_{i,step-k,0} + f_{y,k-2,0}$ ，也就是表示先使用 $step-k$ 步去其他的节点然后回来，然后用一步走到 $y$ ，然后用 $k-2$ 步走出最大价值回到 $y$ 点，最后再用一步回来。
  2. 走到儿子 $y$ 并不回来，最后停留在以 $y$ 为根的子树上。那么可以由 $f_{i,step-k,0}+f_{y,k-1,1}$ 转移，也就是说先用 $step-k$ 步去其他地方然后回来，最后用一步到 $y$ 点，并走出最大价值后不回来。
  3. 走到儿子 $y$ 并不回来，但最后不停留在以 $y$ 为根的子树上，那么可以由 $f_{y,k-2,0}+f_{i,step-k,1}$，也就是先走到 $y$ 子树后回来，再去其他节点，停留在以其他儿子为根的子树上。

那么我们就可以用树形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
47
48
49
50
51
52
53
54
55
#include <bits/stdc++.h>
using namespace std;

const int N = 2010;
int n,k;
int h[N],e[N],ne[N],idx;
void add(int a,int b)
{
	e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
int dp[N][N][2],a[N];
int dep[N];
void dfs(int u,int f) 
{
	dep[u]=dep[f]+1;
	for(int i=0;i<=k;i++) dp[u][i][0]=dp[u][i][1]=a[u];
	for(int g=h[u];g!=-1;g=ne[g])
	{
		if(e[g]==f) continue;
		dfs(e[g],u);
		for(int i=k;i>=0;i--)
		{
			for(int j=i;j>=0;j--)
			{
				if(j>=2)
				{
					dp[u][i][0]=max(dp[u][i][0],dp[u][i-j][0]+dp[e[g]][j-2][0]);
					dp[u][i][1]=max(dp[u][i][1],dp[u][i-j][1]+dp[e[g]][j-2][0]);
				}
				if(j>=1)
				{
					dp[u][i][1]=max(dp[u][i][1],dp[u][i-j][0]+dp[e[g]][j-1][1]);
				}
			}
		}
	}
	
}
int main() 
{
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	memset(h,-1,sizeof h);
	for(int i=1;i<=n-1;i++)
	{
		int a,b;
		scanf("%d%d",&a,&b);
		add(a,b);add(b,a);
	}
	dep[0]=-1;
	dfs(1,0);
	int mx=0;
	for(int i=1;i<=n;i++) mx=max(mx,max(dp[i][k-dep[i]][0],dp[i][k-dep[i]][1]));
	cout<<mx;
}

C树上最远距离

解法

根据直径的性质，其实每个点在树上的最远距离的终点都一定在直径的两个端点上。

所以直接找出直径，然后算出每个点与直径的距离比较大小就好了。

代码

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

const int N = 500010;
int h[N],e[N],ne[N],w[N],idx;
int d[N][2];
void add(int a,int b,int c)
{
	e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
}
int dist[N];
int n;
bool flag[N];

void bfs(int u)
{
	for(int i=1;i<=n;i++) dist[i]=(int)1e9;
	for(int i=1;i<=n;i++) flag[i]=false;
	flag[u]=0;
	dist[u]=0;
	queue<int> q;
	q.push(u);
	while(!q.empty())
	{
		int f=q.front();
		q.pop();
		if(flag[f]) continue;
		flag[f]=1;
		for(int i=h[f];i!=-1;i=ne[i])
		{
			if(dist[f]+w[i]<dist[e[i]])dist[e[i]]=dist[f]+w[i];
			if(!flag[e[i]]) q.push(e[i]);
		}
	}
}
void dfs(int u,int f,int flag)
{
    for(int i=h[u];i!=-1;i=ne[i])
    {
        if(e[i]!=f) d[e[i]][flag]=d[u][flag]+w[i],dfs(e[i],u,flag);
    }
}
int main()
{
	scanf("%d",&n);
	memset(h,-1,sizeof h);
	for(int i=1;i<=n-1;i++)
	{
		int x,c;
        scanf("%d%d",&x,&c);
		add(x,i+1,c);
		add(i+1,x,c);
	}
	bfs(1);
	int id,mx=0;
	for(int i=1;i<=n;i++) 
	{
		if(dist[i]>mx)
		{
			mx=dist[i];
			id=i;
		}
	}
	bfs(id);
	int iid,mxx=0;
	for(int i=1;i<=n;i++)
	{
		if(dist[i]>mxx)
		{
			mxx=dist[i];
			iid=i;
		}
	}
    //cout<<id<<" "<<iid<<endl;
	dfs(id,0,0);
    dfs(iid,0,1);
    for(int i=1;i<=n;i++)
    {
        cout<<max(d[i][0],d[i][1])<<endl;
    }
}

G 树的直径-加强版

解法

首先有一个性质，就是所有直径的公共边都是连续的。

所以我们可以随便找出一条直径，遍历上面的点，从直径的左端点开始，找出每个点不经过直径的最长链，如果发现最长链的长度等于了这个点到右端点的长度，那么右边的边都不可能是公共边了，如图：

我们发现直径上有一个点能延申出的最长路与右端点相等，那么这个点往右的自然都不是公共边了。

同理，还可能出现与往左那段的距离相等的情况，所以在第一轮遍历后还得从这个点再往左遍历，看是否到左端点的距离等于当前点的最长路，两个点区间的边即为答案。

代码

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>
using namespace std;
#define int long long
int n;
const int N = 400010;
int h[N],e[N],ne[N],w[N],idx;
void add(int a,int b,int c)
{
	w[idx]=c,e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
int op,id1,id2;
int flag[N];
int k1;
void dfs1(int u,int f,int sum)
{
	if(sum>op)
	{
		op=sum;
		id1=u;
	}
	for(int i=h[u];i!=-1;i=ne[i])
	{
		if(!flag[e[i]] && e[i]!=f) dfs1(e[i],u,sum+w[i]);
	}
}
int last[N],dist[N];
void dfs2(int u,int f,int sum)
{
	dist[u]=sum;
	if(sum>op)
	{
		op=sum;
		id2=u;
	}
	last[u]=f;
	for(int i=h[u];i!=-1;i=ne[i])
	{
		if(e[i]!=f) dfs2(e[i],u,sum+w[i]);
	}
}
int mm[N];
int next1[N];
int ans=0;
signed main() 
{
	scanf("%lld",&n);
	memset(h,-1,sizeof h);
	for(int i=1;i<=n-1;i++)
	{
		int a,b,c;
		scanf("%lld%lld%lld",&a,&b,&c);
		add(a,b,c);add(b,a,c);
	}
	dfs1(1,1,0);
	op=0;
	k1=id1;
	dfs2(id1,0,0);
	cout<<dist[id2]<<endl;
	for(int i=id2;i!=k1;i=last[i]) next1[last[i]]=i;
	for(int i=id2;i!=0;i=last[i]) flag[i]=1;
	for(int i=id2;i!=0;i=last[i]) op=0,dfs1(i,0,0),mm[i]=op;
	int i;
	i=next1[k1];
	for(;i!=0;i=next1[i])
	{
		if(dist[id2]-dist[i]==mm[i]) break;
	} 	
	for(;i!=0;i=last[i])
	{
		if(dist[i]==mm[i]) break;
		ans++;
	}
	cout<<ans;
}

H 动态树直径

解法

假设我们当前的直径的两个端点是 $x$，$y$，那么假设我们添加了两个点 $a$，$b$，那么根据直径的定理，我们只需要看 $(x,a)$ 和 $(a,y)$ 的长度是否大于原来的直径就行了，因为 $a,b$ 同个深度且父亲相同，所以可以省略 $b$。

路径长度用 $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
#include <bits/stdc++.h>
using namespace std;

const int N = 2000010;
int dp[N][22];
int dep[N];
int n;

int lca(int a,int b)
{
	if(dep[a]>dep[b]) swap(a,b);
	int k=dep[b]-dep[a];
	for(int i=21;i>=0;i--)
	{
		if(k&(1<<i)) b=dp[b][i];
	}
	if(a==b) return a;
	for(int i=21;i>=0;i--)
	{
		if(dp[a][i]!=dp[b][i]) a=dp[a][i],b=dp[b][i];
	}
	return dp[a][0];
}
int main()
{
	scanf("%d",&n);
	for(int i=0;i<=21;i++) dp[1][i]=dp[2][i]=dp[3][i]=dp[4][i]=1;
	dep[2]=dep[3]=dep[4]=1;
	int d=5;
	int id1=4,id2=2,len=2;
	while(n--)
	{
		int x;
		scanf("%d",&x);
		dp[d][0]=dp[d+1][0]=x;
		for(int i=1;i<=20;i++) dp[d][i]=dp[d+1][i]=dp[dp[d][i-1]][i-1];
		dep[d]=dep[d+1]=dep[x]+1;
		
		int aa=lca(d,id1),bb=lca(d,id2);
		int g=dep[d]+dep[id1]-2*dep[aa];
		int gg=dep[d]+dep[id2]-2*dep[bb];
		if(g>len) len=g,id2=id1,id1=d;
		if(gg>len) len=gg,id1=id2,id2=d;
		printf("%d\n",len); 
		d+=2;
	}
}

I 不相交路径

解法

可以贪心，首先按照路径的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
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
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define clr(f, n) memset(f, 0, sizeof(int) * (n))
#define cpy(f, g, n) memcpy(f, g, sizeof(int) * (n))
#define rev(f, n) reverse(f, f + n)
#define pir pair<int, int>
#define mkp make_pair
#define fst it->first
#define sec it->second
#define int long long
#define up(i,x,y) for(int i=x,i##end=y;i<=i##end;++i)
#define down(i,x,y) for(int i=x,i##end=y;i>=i##end;--i)
#define graph(i,x) for(int i=head[x];i;i=nxt[i])
using namespace std;
int n, m, k;
int read()
{
    int s = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        s = s * 10 + ch - '0';
        ch = getchar();
    }
    return s * f;
}
inline void print(int *f, int len)
{
    for (int i = 0; i < len; i++)
        printf("%lld ", f[i]);
    puts("");
}
const int maxn=2e5+10;
int head[maxn],to[maxn],nxt[maxn],tot;
int f[maxn][18],dep[maxn];
void add(int a,int b)
{
	to[++tot]=b;
	nxt[tot]=head[a];
	head[a]=tot;
}
void dfs(int x,int fa)
{
	f[x][0]=fa;
	up(i,1,17)f[x][i]=f[f[x][i-1]][i-1];
	dep[x]=dep[fa]+1;
	for(int i=head[x];i;i=nxt[i])
	{
		int v=to[i];
		if(v==fa)continue;
		dfs(v,x);
	}
}
int lca(int a,int b)
{
	if(dep[a]<dep[b])swap(a,b);
	down(i,17,0)
	{
		if(dep[f[a][i]]>=dep[b])a=f[a][i];
	}
	if(a==b)return a;
	down(i,17,0)
	{
		if(f[a][i]!=f[b][i])a=f[a][i],b=f[b][i];
	}
	return f[a][0];
}
struct node
{
	int u,v;
	int lca;
}q[maxn];
bool cmp(node a,node b)
{
	return dep[a.lca]>dep[b.lca];
}
int vis[maxn];
void dfs1(int x)
{
	vis[x]=1;
	for(int i=head[x];i;i=nxt[i])
	{
		int v=to[i];
		if(vis[v]||v==f[x][0])continue;
		dfs1(v);
	}
}
signed main()
{
	n=read(),m=read();
	up(i,1,n-1)
	{
		int a=read(),b=read();
		add(a,b),add(b,a);
	}
	dfs(1,0);
//	cout<<f[3][0];
	up(i,1,m)
	{
		q[i].u=read(),q[i].v=read();
		q[i].lca=lca(q[i].u,q[i].v);
		//cout<<q[i].lca<<endl;
	}
//	cout<<endl;
	sort(q+1,q+m+1,cmp);
	int ans=0;
	up(i,1,m)
	{
		if(vis[q[i].u]||vis[q[i].v])continue;
		++ans;
		dfs1(q[i].lca);
	}
	
	cout<<ans;
}