题目链接
続く日めくりカレンダー
一页页翻过的日历延续着
在【数据删除】遇到的题目，纯乱搞题。如果放在 OI 赛制，我估计是要被喷的。 得亏是 IOI 严格。
考虑一下最唐的DP，定义 \(f[i][j][k]\) 表示 \(i\) 子树，分成 \(j\) 段，当前答案为 \(j\)，转移是显然的，这里不再赘述。这样的作法复杂度来到了 \(O(n^2 val^2)\)，显然是过不去的。
一个很明显的策略是减少状态数。我们可以发现如果 \(f[i][j][k_1] \le f[i][j][k_2]\) 且 \(k_1 < k_2\)，那么 \(k_2\) 就肯定不会产生贡献，也就不用记录并转移。这样子状态数可以少很多。由于数据随机，因此出题人无法卡我们，因此跑的很快。
我是奶龙，因此不会分析复杂度。但反正过了。
Code
#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define fi first
#define se second
#define IOS ios::sync_with_stdio(false);cin.tie(0),cout.tie(0)
#define File(s) freopen(s".in","r",stdin);freopen(s".out","w",stdout)
const int N = 305;
const LL INF = 1e18;
vector< pair< LL , LL > > dp[N][N];//i节点 j块 fi:k,se:ans
vector< pair< LL , LL > > tmp[N];//临时的
LL a[N];
int n;
int siz[N];
vector<int> G[N];
void dfs(int u,int fa){siz[u] = 1;dp[u][1].push_back({a[u],a[u] * a[u]});for(int v : G[u]){if(v == fa) continue;dfs(v,u);for(int i=1;i<=siz[v];i++)for(int j=1;j<=siz[u];j++){for(pair<LL,LL> x : dp[v][i])for(pair<LL,LL> y : dp[u][j]){tmp[i+j-1].push_back({x.first + y.first,x.second + y.second + 2 * x.first * y.first});tmp[i+j].push_back({y.first,x.second + y.second});}}siz[u] += siz[v];for(int i=1;i<=siz[u];i++){sort(tmp[i].begin(),tmp[i].end());dp[u][i].clear();LL minn = INF;for(pair<LL,LL> x : tmp[i]){if(minn > x.se){dp[u][i].push_back(x);minn = x.se;}}tmp[i].clear();}}
}
void solve(){for(int i=1;i<=n;i++){siz[i] = 0;G[i].clear();tmp[i].clear();for(int j=1;j<=n;j++)dp[i][j].clear();}cin >> n;for(int i=1;i<=n;i++)cin >> a[i];for(int i=1;i<n;i++){int u,v;cin >> u >> v;G[u].push_back(v);G[v].push_back(u);}dfs(1,0);for(int i=1;i<=n;i++){int siz = dp[1][i].size();cout << dp[1][i][siz-1].se << " ";}cout << "\n";
}
int main()
{int T;IOS;// File("tree");cin >> T;while(T -- ) solve();return 0;
}