盈利型网站,软件开发的过程,有什么好的加盟店项目,改进网站建设英文作文U66905 zz题 考虑一个点权值被计算了多少次。。。不知 所以对未来承诺#xff0c;方便直接算上总数#xff01; 然后其实是给边定向#xff0c;即先删除fa和son的哪一个 f[x][j]#xff0c;会计算j次 无法转移 f[x][j][k]#xff0c;其中会从子树计算k次。 当边从儿子指向…U66905 zz题 考虑一个点权值被计算了多少次。。。不知 所以对未来承诺方便直接算上总数 然后其实是给边定向即先删除fa和son的哪一个 f[x][j]会计算j次 无法转移 f[x][j][k]其中会从子树计算k次。 当边从儿子指向父亲枚举就是O(n^4)的了还不能sz剪枝 转移是O(n^4)的 其实这里记录一个前缀和之类的就行了 可以用f[i][j]仅往i子树里选择j个最大值 g[i][j]往i子树外额外选择j个最大值 然后就可以转移了 注意 权值有负数而每个儿子强制必须选的所以不能累计取max // luogu-judger-enable-o2
#pragma GCC optimize(O3,Ofast,inline,unroll-all-loops,-ffast-math)
#pragma GCC target(avx,sse2,sse3,sse4,popcnt)
#includebits/stdc.h
#define reg register int
#define il inline
#define fi first
#define se second
#define mk(a,b) make_pair(a,b)
#define numb (ch^0)
using namespace std;
typedef long long ll;
templateclass Til void rd(T x){char ch;x0;bool flfalse;while(!isdigit(chgetchar()))(ch-)(fltrue);for(xnumb;isdigit(chgetchar());xx*10numb);(fltrue)(x-x);
}
templateclass Til void output(T x){if(x/10)output(x/10);putchar(x%100);}
templateclass Til void ot(T x){if(x0) putchar(-),x-x;output(x);putchar( );}
templateclass Til void prt(T a[],int st,int nd){for(reg ist;ind;i) ot(a[i]);putchar(\n);}namespace Miracle{
const int N401;
const ll inf0x3f3f3f3f3f3f3f3f;
int n;
struct node{int nxt,to;
}e[2*N];
int hd[N],cnt;
ll d[N];
void add(int x,int y){e[cnt].nxthd[x];e[cnt].toy;hd[x]cnt;
}
ll h[N][N][N];
ll f[N][N],g[N][N];
int sz[N];
void dfs(int x){
// cout dfs xendl;sz[x]1;for(reg j1;jn;j){h[x][j][1]d[x]*j;}
// bool flfalse;for(reg ihd[x];i;ie[i].nxt){int ye[i].to;dfs(y);
// fltrue;for(reg j1;jn;j){for(reg kmin(j,sz[x]sz[y]);k1;--k){ll oldh[x][j][k];h[x][j][k]-0x3f3f3f3f3f3f3f3f;for(reg pmin(sz[x],k-1);p1;--p){h[x][j][k]max(h[x][j][k],h[x][j][p]f[y][k-p]);}h[x][j][k]max(h[x][j][k],oldg[y][j]);}}sz[x]sz[y];}
// cout now xendl;
// if(!fl){
// cout leaf endl;
// for(reg j1;jn;j){
// h[x][j][1]d[x]*j;
// }
// }for(reg j1;jn;j){
// cout jjj jendl; f[x][j]h[x][j][j];for(reg k1;ksz[x]kjn;k){g[x][j]max(g[x][j],h[x][jk][k]);}
// cout f f[x][j] g g[x][j] endl;}
}
int main(){rd(n);for(reg i1;in;i) rd(d[i]);int y0;for(reg x2;xn;x){rd(y);add(y,x);}memset(h,0xcf,sizeof h);memset(f,0xcf,sizeof f);memset(g,0xcf,sizeof g);dfs(1);ll ans-0x3f3f3f3f3f3f3f3f;for(reg j1;jn;j){ansmax(ans,f[1][j]);}printf(%lld,ans);return 0;
}}
signed main(){
// freopen(data.in,r,stdin);
// freopen(my.out,w,stdout);Miracle::main();return 0;
}/*Author: *Miracle*Date: 2019/3/29 20:22:41
*/ View Code 转载于:https://www.cnblogs.com/Miracevin/p/10624555.html
