网站可做2个首页吗,免费发帖的平台有哪些,微网站与微信公众号,宝格丽网站建设策划案2023牛客暑期多校训练营6-A Tree
https://ac.nowcoder.com/acm/contest/57360/A 文章目录 2023牛客暑期多校训练营6-A Tree题意解题思路代码 题意 解题思路
最大价值和这个数据范围#xff0c;一眼 d p dp dp。
直接在树上并不好处理#xff0c;问题是如何有效转化、处理…2023牛客暑期多校训练营6-A Tree
https://ac.nowcoder.com/acm/contest/57360/A 文章目录 2023牛客暑期多校训练营6-A Tree题意解题思路代码 题意 解题思路
最大价值和这个数据范围一眼 d p dp dp。
直接在树上并不好处理问题是如何有效转化、处理 x , y x,y x,y之间的最短路径上的最大边权值。这里用到了 k r u s k a l 重构树 kruskal重构树 kruskal重构树 k r u s k a l 算法 kruskal算法 kruskal算法是一种贪心地求最小生成树的算法本题所用算法参照了该算法的思路将一张无向图的边按边权排序一次取用不同的是我们将每条边转化为带有点权的虚点任意两点由虚点连接而原图上的点均为叶子结点如图 一条边的两个端点将祖先连在一起可以用并查集实现。
根据这种树的特殊性质其虚点的权值自上而下减少原图上两个点之间的最短路径上的最大权值即为该图上两点最近公共祖先的点权。此时可以进行树形 d p dp dp了 设 d p x , b dp_{x,b} dpx,b表示以 x x x为根的字数内黑点个数为 b b b的贡献最大值对于原图上任意边其贡献值为 ( W 1 × B 2 W 2 × B 1 ) × k (W_1\times B_2W_2\times B_1)\times k (W1×B2W2×B1)×k推理得 d p x , b M a x b − s z r ≤ b 1 ≤ m i n ( b , s z l ) ( d p l , b 1 d p r , b − b 1 k x × ( b 1 ( 左子树黑点个数 ) × ( s z r − b b 1 ) ( 右子树白点个数 ) ( s z l − b 1 ) ( 左子树白点个数 ) × ( b − b 1 ) ( 右子树黑点个数 ) ) ) dp_{x,b}Max_{b-sz_r\le b_1\le min(b,sz_l)}(dp_{l,b_1}dp_{r,b-b_1}\\ k_x\times(b_1(左子树黑点个数)\times(sz_r-bb_1)(右子树白点个数)\\ (sz_l-b_1)(左子树白点个数)\times(b-b_1)(右子树黑点个数))) dpx,bMaxb−szr≤b1≤min(b,szl)(dpl,b1dpr,b−b1kx×(b1(左子树黑点个数)×(szr−bb1)(右子树白点个数)(szl−b1)(左子树白点个数)×(b−b1)(右子树黑点个数))) 对于叶子结点 l e a f leaf leaf d p l e a f , a [ l e a f ] ⊕ 1 − c o s t l e a f d p l e a f , a [ l e a f ] 0 dp_{leaf,a[leaf]\oplus 1}-cost_{leaf}\\ dp_{leaf,a[leaf]}0 dpleaf,a[leaf]⊕1−costleafdpleaf,a[leaf]0
注意内存与结果大小 d p dp dp数组可以用 v e c t o r l o n g l o n g vectorlong long vectorlonglong。
代码
#includebits/stdc.h
#define ll long long
#define pb push_back
using namespace std;
const int N6005;
int n,a[N],c[N],f[N],m,sz[N],b[N];
pairint,inte[N];
struct node{int u,v,w;
}p[N];
vectorll dp[N];
bool cmp(node a,node b){return a.wb.w;
}
int sf(int x){if(f[x]x)return x;return f[x]sf(f[x]);
}
void dfs(int u){if(un){dp[u][a[u]^1]-c[u];dp[u][a[u]]0;sz[u]1;return;}int le[u].first,re[u].second;dfs(l),dfs(r);sz[u]sz[l]sz[r];dp[u]vectorll(sz[u]1,-0x3f3f3f3f3f3f);if(sz[l]sz[r])swap(l,r);for(int x0;xsz[u];x)for(int imax(0,x-sz[r]);imin(sz[l],x);i){dp[u][x]max(dp[u][x],dp[l][i]dp[r][x-i]b[u]*(i*(sz[r]-xi)(sz[l]-i)*(x-i)));}
}
int main(){cinn;for(int i1;in;i)cina[i],dp[i].resize(2);for(int i1;i2*n;i)f[i]i;for(int i1;in;i)cinc[i];for(int i1;in;i){int u,v,w;cinuvw;p[i].uu,p[i].vv,p[i].ww;}sort(p1,pn,cmp);mn;for(int i1;in;i){int up[i].u,vp[i].v,wp[i].w;if(sf(u)sf(v))continue;m;b[m]w;e[m].firstsf(u),e[m].secondsf(v);f[sf(u)]f[sf(v)]m;}dfs(sf(1));ll ans0;for(int i0;in;i){ansmax(ans,dp[sf(1)][i]);}coutans;
}
