A

我们可以设 $f_{i,0/1}$ 为第 $i$ 个点选不选，那么一个点选了自然就是加上所有儿子节点不选的状态，不选就是加上所有儿子选和不选的较大值。

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

const int N = 100010;
int h[N],e[N],ne[N],idx;
int a[N],f[N][2];
int n;
void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void dfs(int u,int fa)
{
    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(0,f[e[i]][0]);
        }
    }
}
int main()
{
    scanf("%d",&n);
    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);
    }
    dfs(1,0);
    printf("%d",max(f[1][0],f[1][1]));
}

B

我们可以设 $f_{i,j,0/1}$ 表示当前走到 $i$ 节点，走 $j$ 步，是否回到原节点的最大价值。

那么我们可以枚举当前的步数和子节点 $v$ 走的步数 $l$，则有

$dp_{i,j,1}=dp_{v,l,1}+dp_{i,j-l-2,1}$

意为从子节点走 $l$ 步回来再加上其他节点走 $j-l-2$（与子节点来回的步数要减二）的最大价值。

而不回来的则有：

$dp_{i,j,0}=dp_{v,l,0}+dp_{i,j-l-1,1}$

意为从子节点走不回来了加上从其他节点走 $j-l-1$ 步后回来。

还有

$dp_{i,j,0}=dp_{v,l,1}+dp_{i,j-l-2,0}$

意为从儿子节点走 $l$ 步回来加上 从其他节点走$i-j-2$ 步不回来了。因为不一定是停留在 $v$ 点，所以要加上这条转移方程。

代码

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

const int N = 201;
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 a[200010];
int n,k;
int dp[N][N][2];

void dfs(int u,int f)
{
	for(int i=0;i<=k;i++) dp[u][i][0]=dp[u][i][1]=a[u];
	for(int i=h[u];i!=-1;i=ne[i])
	{
		if(e[i]!=f)
		{
			dfs(e[i],u);
			for(int j=k;j>=0;j--)
			{
				for(int l=0;l<=j;l++)
				{
					if(j-l>=1)dp[u][j][0]=max(dp[u][j][0],dp[e[i]][l][0]+dp[u][j-l-1][1]);
					
					if(j-l>=2) 
					{
						dp[u][j][0]=max(dp[u][j][0],dp[u][j-l-2][0]+dp[e[i]][l][1]);
						dp[u][j][1]=max(dp[u][j][1],dp[e[i]][l][1]+dp[u][j-l-2][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);
	}
	dfs(1,0);
	printf("%d",max(dp[1][k][0],dp[1][k][1]));
}

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

const int N = 200001;
int h[N],e[N],ne[N],w[N],idx;
void add(int a,int b,int c)
{
	e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
int a[200010];
int n,k;
int d1[N],d2[N];
void dfs1(int u,int f)
{
	for(int i=h[u];i!=-1;i=ne[i])
	{
		if(e[i]!=f)
		{
			d1[e[i]]=d1[u]+w[i];
       //     cout<<e[i]<<" "<<u<<" "<<w[i]<<endl;
			dfs1(e[i],u);
		}
	}
}
void dfs2(int u,int f)
{
	for(int i=h[u];i!=-1;i=ne[i])
	{
		if(e[i]!=f)
		{
			d2[e[i]]=d2[u]+w[i];
	//		cout<<e[i]<<" "<<u<<" "<<w[i]<<endl;
			dfs2(e[i],u);
		}
	}
}
int main()
{	
	scanf("%d",&n);
    memset(h,-1,sizeof h);
	for(int i=1;i<=n-1;i++)
	{
		int a,c;
		scanf("%d%d",&a,&c);add(a,i+1,c);add(i+1,a,c);
	}
	dfs1(1,0);
	int id=0,mx=-1e9;
	for(int i=1;i<=n;i++)
	{
		if(d1[i]>mx)
		{
			mx=d1[i];
			id=i;
		}
	}
	dfs2(id,0);mx=-1e9,id=0;
    for(int i=1;i<=n;i++)
    {
        if(d2[i]>mx) mx=d2[i],id=i;
    }
    d1[id]=0;
    dfs1(id,0);
	for(int i=1;i<=n;i++) printf("%d\n",max(d1[i],d2[i]));
}

D

首先，如果只有一个机器人j并返回根节点，那么最小花费一定是二乘以边权的总和。

那么如果派出的机器人遍历完子树要返回根节点，一定只返回一个，因为如果一起回来的话要多好几条边权，而遍历的区域却是一样的。

那么对于每个儿子，要么只派一个并返回根节点，要么派多个。

设 $f_{i,j}$ 表示用 $j$ 个机器人遍历以 $i$ 为根的子树所需要的代价。

而派出一个的状态应是：

$f_{i,j}+=f_{v,0}+2*w_i$

因为派出了一个又返回，相当于没派出。

而剩下的则类似一个背包问题，每个儿子节点派出多少个机器人：

$f_{i,j}=min(f_{i,j},f_{i,j-l}+f_{v,l}+l*w_i)$

派 $l$ 个机器人走，则要算 $l$ 次与儿子联通的边。

最后还记得要预处理 $f_{i,0}$ 表示机器人为后面的机器人回来做准备。

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
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 20001;
int h[N],e[N],ne[N],w[N],idx;
void add(int a,int b,int c)
{
	e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
int n,s,k;
int dp[N][50];

void dfs(int u,int f)
{
	for(int i=h[u];i!=-1;i=ne[i])
	{
		if(e[i]==f) continue;
		dfs(e[i],u);
		for(int j=k;j>=1;j--)
		{
			dp[u][j]+=dp[e[i]][0]+2*w[i];
			for(int l=1;l<=j;l++) dp[u][j]=min(dp[u][j],dp[u][j-l]+dp[e[i]][l]+l*w[i]);
		}
		dp[u][0]+=2*w[i]+dp[e[i]][0];
	}
}

signed main()
{	
	scanf("%lld%lld%lld",&n,&s,&k);
	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);
	}
	dfs(s,s);
	printf("%lld",dp[s][k]);
}

E

我们可以设 $f_{i,j}$ 为在 $i$ 的子树内有多少个点走 $j$ 步能到点 $i$。

那么答案自然是：

$ans+=f_{i,j}*f_{v,k-j-1}$

走 $j$ 步到 $i$ 的点数乘上走 $k-j-1$ 步到儿子节点的点数，刚好为对于这个儿子的方案数。

那么我们可以递归边计算答案边更新 $f$ 数组。

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

const int N = 500010;
int dp[N][501];
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 n,m;
long long s=0;
void dfs(int u,int f)
{
	for(int i=h[u];i!=-1;i=ne[i])
	{
        if(e[i]==f) continue;
        dfs(e[i],u);
		for(int j=1;j<m;j++) s+=dp[u][j]*dp[e[i]][m-j-1];
		for(int j=1;j<=m;j++) dp[u][j]+=dp[e[i]][j-1];
	}
	s+=dp[u][m];
}
int main()
{
	scanf("%d%d",&n,&m);
	memset(h,-1,sizeof h);
	for(int i=1;i<=n;i++) dp[i][0]=1;
	for(int i=1;i<=n-1;i++)
	{
		int a,b;
		scanf("%d%d",&a,&b);
		add(a,b);add(b,a);
	}
	dfs(1,1);
	cout<<s;
}

F

首先，所有相邻的颜色都会一次操作改变，所以我们可以直接把所有相邻的相同的颜色看成一个点。

那么，新的树一定是黑白相间的，我们自然就是要把那些黑的改成白的或者白的改成黑的，也就是直径长度的一半。

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

const int N = 500010;
int a[N];
int h[N],e[N],ne[N],idx,w[N];
void add(int a,int b,int c)
{
	e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
int mx[N];
int n;
int ans=0;
void dfs(int u,int f)
{
	for(int i=h[u];i!=-1;i=ne[i])
	{
		if(e[i]!=f)
		{
			dfs(e[i],u);
            ans=max(ans,mx[u]+w[i]+mx[e[i]]);
            mx[u]=max(mx[u],mx[e[i]]+w[i]);
		}
	}
}
int main()
{
	scanf("%d",&n);
	memset(h,-1,sizeof h);
	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);
		int c=(a[x]==a[y]?0:1);
		add(x,y,c);add(y,x,c);
	}
	dfs(1,1);
	printf("%d",(ans+1)/2);
}

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$，那么新加入两个点，如果直径被更新了，那么只有 $x,n+1$ 或 $y,n+1$ 两种可能，因为一次只加两个点，所以可以每次加入点时更新 $lca$ 的 $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
#include <bits/stdc++.h>
using namespace std;

const int N = 2000010;
 
int dp[N][25];
int dep[N];
int q;
int cnt=4;
int lca(int a,int b)
{
	if(dep[a]<dep[b]) swap(a,b);
	int k=dep[a]-dep[b];
	for(int i=21;i>=0;i--)
	{
		if(k&(1<<i)) a=dp[a][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",&q);
	for(int i=0;i<=21;i++) dp[1][i]=1,dp[2][i]=dp[3][i]=dp[4][i]=1;
	dep[2]=dep[3]=dep[4]=2;dep[1]=1;
	int x=3,y=2,mx=2;
	while(q--)
	{
		int v;
		scanf("%d",&v);
		dep[cnt+1]=dep[cnt+2]=dep[v]+1;
		dp[cnt+1][0]=dp[cnt+2][0]=v;
		for(int i=1;i<=21;i++) dp[cnt+1][i]=dp[dp[cnt+1][i-1]][i-1],dp[cnt+2][i]=dp[dp[cnt+2][i-1]][i-1];
		int xx=x,yy=y;
		int aa=dep[cnt+1]+dep[xx]-2*dep[lca(cnt+1,x)],bb=dep[cnt+1]+dep[yy]-2*dep[lca(cnt+1,y)];
		if(aa>mx) y=x,x=cnt+1,mx=aa;
		if(bb>mx)
		{
			x=y,y=cnt+1;
			mx=bb;
		}
		printf("%d\n",mx);
		cnt+=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
#include <bits/stdc++.h>
using namespace std;

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;
}
const int N = 200010;

int h[N],e[N],ne[N],idx=1,dp[N][18],dep[N];
int n,m;
void add(int a,int b){e[idx]=b,ne[idx]=h[a],h[a]=idx++;}
void dfs(int u,int f)
{
	dp[u][0]=f;dep[u]=dep[f]+1;
	for(int i=1;i<=17;i++) dp[u][i]=dp[dp[u][i-1]][i-1];
	for(int i=h[u];i;i=ne[i])
	{
		if(e[i]!=f) dfs(e[i],u);
	}
}
int lca(int a,int b)
{
	if(dep[a]<dep[b]) swap(a,b);
	int k=dep[a]-dep[b];
	for(int i=0;i<=17;i++)
	{
		if(k&(1<<i)) a=dp[a][i];
	}
	if(a==b) return a;
	for(int i=17;i>=0;i--)
	{
		if(dp[a][i]!=dp[b][i]) a=dp[a][i],b=dp[b][i];
	}
	return dp[a][0];
}
struct node
{
	int a,b,lc;
};
bool cmp(node x,node y)
{
	return dep[x.lc]>dep[y.lc];
}
node a[N];
bool vis[N];
void dfs1(int u,int f)
{
	vis[u]=1;
	for(int i=h[u];i;i=ne[i]) if(e[i]!=f && !vis[e[i]]) dfs1(e[i],u);
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n-1;i++)
	{
		int a,b;a=read();b=read();
		add(a,b);add(b,a);
	}
	dfs(1,1);
	for(int i=1;i<=m;i++)
	{
		a[i].a=read(),a[i].b=read();a[i].lc=lca(a[i].a,a[i].b);
	}
	sort(a+1,a+m+1,cmp);
	int ans=0;
	for(int i=1;i<=m;i++)
	{
		if(vis[a[i].a] || vis[a[i].b]) continue;
		ans++;
		dfs1(a[i].lc,dp[a[i].lc][0]);
	}
	printf("%d",ans);
}