XJTUOJ 校赛模拟赛G

校赛模拟赛这个G其实场上有这个思路,但是这道题的$dp$转移还是很容易写错的.尤其是初值的问题,要考虑清楚$dp$的意义,以下的题解中的$dp$方式有点奇怪,可能并非最简单的$dp$方式,不过也足以通过这道题.

考虑如何计算奇数偶数路径数,其实就是黑白染色,记黑色的点$x$个,白色的点$y$个,我们要最大化的
就是$\sum ((x-y)^2-(x+y))$,其实就是要最大化前面那个东西.

考虑一个$dp$,$dp[u][p]$表示考虑现在与u联通的点$(x-y)$的值是$p$的时候其余的连通块的
$\sum (x-y)^2$.

显然可以得到转移:$dp[u][p+q]=\max (dp[v][p]+dp[u][q])$

这里有个必须要注意的一点是:转移完了以后是要重新计算$dp[u][0]$的.

理由是:我们考虑的是不与根联通的连通块的平方和.做完当前$dp$后,$u$是与$fa[u]$断开的,那么下次考虑不连接这个子树的时候,即$u$与$fa[u]$不连通,那么$u$的贡献依旧是$dp[u][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
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
/*
* @Author: RBQRBQ
* @Date: 2020-04-25 23:09:46
* @LastEditors: RBQRBQ
* @LastEditTime: 2020-04-25 23:33:48
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef pair<int,int> pii;
namespace IO{
template<typename T>inline void read(T &x){
x=0;ll f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-f;ch=getchar();}
while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}
x=x*f;
}
}
using namespace IO;
const int maxn=5000+10;
VI G[maxn];
int n;
void addedge(int x,int y)
{
G[x].push_back(y),G[y].push_back(x);
}
ll unused[maxn][maxn<<1];
ll unused2[maxn][maxn<<1];
ll *dp[maxn];//dp array
ll *dp2[maxn];//scrolling array
ll siz[maxn];//size of subtree
int color[maxn];//B or W array
const ll INF=10000000000000ll;
void pre(int u,int fa,int c)
{
color[u]=c;
for(int i=0;i<G[u].size();i++)
{
int v=G[u][i];
if(v==fa) continue;
pre(v,u,-c);
}
}
ll ans=-INF;
void dfs(int u,int fa)
{
ans=-INF;
siz[u]=1;
for(int k=-siz[u];k<=siz[u];k++)
dp[u][k]=-INF;
dp[u][color[u]]=0;
for(int i=0;i<G[u].size();i++)
{
int v=G[u][i];
if(v==fa) continue;
dfs(v,u);
for(int k=-siz[u]-siz[v];k<=siz[u]+siz[v];k++)
dp2[u][k]=-INF;
for(int k=-siz[u];k<=siz[u];k++)
for(int j=-siz[v];j<=siz[v];j++)
dp2[u][k+j]=max(dp[u][k]+dp[v][j],dp2[u][k+j]);
siz[u]+=siz[v];
for(int k=-siz[u];k<=siz[u];k++)
dp[u][k]=dp2[u][k];
}
for(int k=-siz[u];k<=siz[u];k++)
ans=max(ans,dp[u][k]+k*k);
dp[u][0]=ans;//updata dp[u][0]


}
int main()
{
read(n);
for(int i=1;i<=n;i++) dp[i]=unused[i]+maxn;
for(int i=1;i<=n;i++) dp2[i]=unused2[i]+maxn;
for(int i=1;i<n;i++)
{
int x,y;read(x),read(y);
addedge(x,y);
}
pre(1,1,1);
dfs(1,1);
cout<<ans-n;
return 0;

}