注：由于官方数据还没公布，所以代码不一定保熟
本来想在上一篇题解里放代码，但是这样文章就太长了，所以新开一篇文章放代码
d2t1：
#include<bits/stdc++.h>
#define gc getchar()
#define pc putchar
#define li long long
using namespace std;
inline li read(){
li x = 0;
int y = 0,c = gc;
while(c < '0' || c > '9') y = c,c = gc;
while(c >= '0' && c <= '9') x = x * 10 + c - '0',c = gc;
return y == '-' ? -x : x;
}
inline void prt(li x){
if(x >= 10) prt(x / 10);
pc(x % 10 + '0');
}
inline void print(li x){
if(x < 0) pc('-'),x = -x;
prt(x);
}
inline void file(char *s){
char c[50];
sprintf(c,"%s.in",s);
freopen(c,"r",stdin);
sprintf(c,"%s.out",s);
freopen(c,"w",stdout);
}
li s1 = 19260817,s2 = 23333333,s3 = 998244853,srd;
inline li rd(){
return srd = (srd * s1 + s2 + rand()) % s3;
}
int p[2010],cnt,n,m,dy[2010],wei[10010];
bool notp[2010];
int sl[8200][310],ss[2010],a[310],k,zc[2010],bg[2010],tto[8210];
const int mo = 998244353;
li mi[1000010];
bool vis[2010];
int main(){
srand(time(0));rd();
//file("card");
int i,j,x,l;
for(i = 1;i < (1 << 13);++i) wei[i] = wei[i >> 1] ^ (i & 1);
notp[1] = 1;
for(i = 2;i <= 2000;++i){
if(!notp[i]) p[++cnt] = i,dy[i] = cnt;
for(j = 1;j <= cnt && i * p[j] <= 2000;++j){
notp[i * p[j]] = 1;
if(i % p[j] == 0) break;
}
}
n = read();
mi[0] = 1;for(i = 1;i <= n;++i) mi[i] = mi[i - 1] * 2 % mo;
for(i = 1;i <= n;++i){
++ss[read()];
}
for(i = 14;i <= cnt;++i) for(j = 1;p[i] * j <= 2000;++j) bg[p[i] * j] = i;
for(i = 1;i <= 2000;++i) for(j = 1;j <= 13;++j)
if(i % p[j] == 0) zc[i] |= (1 << j - 1);
for(i = 0;i < (1 << 13);++i){//不能出现的因子集合
for(j = 1;j <= 2000;++j) if((i & zc[j]) == 0){
sl[i][bg[j]] += ss[j];
tto[i] += ss[j];
}
}
m = read();
li qqq = 0;
for(i = 1;i <= m;++i){
k = read();
int r = 0,q = 0;
memset(vis,0,sizeof(vis));
for(j = 1;j <= k;++j){
x = read();
if(vis[x]) continue;
vis[x] = 1;
if(x <= 41) q |= 1 << (dy[x] - 1);
else a[++r] = dy[x];
}
li ans = 0;
for(j = q;;j = (j - 1) & q){
int *g = sl[j];
li tmp = 1;
int oo = tto[j];
for(l = 1;l <= r;++l){
(tmp *= mi[g[a[l]]] - 1) %= mo;
oo -= g[a[l]];
}
(tmp *= mi[oo]) %= mo;
if(wei[j]) ans -= tmp;
else ans += tmp;
if(!j) break;
}
print((ans % mo + mo) % mo);pc('\n');
}
return 0;
}
d2t2：
#include<bits/stdc++.h>
#define gc getchar()
#define pc putchar
#define li long long
using namespace std;
inline li read(){
li x = 0;
int y = 0,c = gc;
while(c < '0' || c > '9') y = c,c = gc;
while(c >= '0' && c <= '9') x = x * 10 + c - '0',c = gc;
return y == '-' ? -x : x;
}
inline void prt(li x){
if(x >= 10) prt(x / 10);
pc(x % 10 + '0');
}
inline void print(li x){
if(x < 0) pc('-'),x = -x;
prt(x);
}
inline void file(char *s){
char c[50];
sprintf(c,"%s.in",s);
freopen(c,"r",stdin);
sprintf(c,"%s.out",s);
freopen(c,"w",stdout);
}
li s1 = 19260817,s2 = 23333333,s3 = 998244853,srd;
inline li rd(){
return srd = (srd * s1 + s2 + rand()) % s3;
}
int n,a[500010],x,y;
char c[1000010];
vector<li> p[500010];
multiset<li> ss;
int mx;
li wk(int qs){
int i,j;
li qjmx = 0;int mxwz = 0;bool fg = 0;
li ans = 0,mm,nn,cd;
int sz,sl = ss.size();
for(i = qs;i <= mx;++i){//找全局最大值，值为qjmx，位置为mxwz
sz = p[i].size();
if(sz > 1) fg = 1;
if(fg){
if(p[i][sz - 1] >= qjmx){
qjmx = p[i][sz - 1];
mxwz = i;
}
}
}
for(i = qs;i <= n;++i){
//每一层用最小的把剩下的放进去，最后用最大的把最小的放进去
int sz = i <= mx ? p[i].size() : 0;
sl += sz;
if(sl <= 1){sl = 0;continue;}
for(j = 0;j < p[i].size();++j) ss.insert(p[i][j]);
mm = *ss.begin();//当前最小值
nn = *ss.rbegin();//当前最大值
if(i < mxwz){//还没遇到最大值
ans += mm * (sl - 2) + nn;//这一层的权值是mn*(sl-2)+mx
--sl;ss.erase(ss.find(nn));//这一层留下最大值
}
else{//已经遇到了最大值
cd = *(++ss.rbegin());//当前次大值
ans += mm * (sl - 2) + cd;//这一层的权值是mn*(sl-2)+cd
--sl;ss.erase(ss.find(cd));//这一层留下次大值
}
}
ss.clear();
return ans;
}
int main(){
srand(time(0));rd();
//file("bracket");
int i,j;
n = read();x = read();y = read();
scanf("%s",c + 1);
int nw = 0;
for(i = 1,j = 1;i <= n;++i,++j){
while(c[j] == ')') --nw,++j;
p[++nw].push_back(read());
mx = max(mx,nw);
}
for(i = 1;i <= mx;++i) sort(p[i].begin(),p[i].end());
li ans = 0,mm = 1e9,nn = 0,tot = 0;
int sl = 0;
int qs = 0;
for(qs = 1;qs <= mx;++qs) if(p[qs].size() > 1) break;
if(qs == mx + 1){
pc('0');pc('\n');return 0;
}
if(x == 1 && y == 1){//每层用最小的把别的放进去，在外面留一个最大的
for(i = qs;i <= n;++i){
int sz = i <= mx ? p[i].size() : 0;
sl += sz;
if(sl <= 1){sl = 0;continue;}
for(j = 0;j < p[i].size();++j){
tot += p[i][j];
ss.insert(p[i][j]);
}
mm = *ss.begin();//当前最小值
nn = *ss.rbegin();//当前最大值
ans += tot + mm * (sl - 2);//这一层的权值是sum+mn*(sl-2)
--sl;tot -= nn;ss.erase(ss.find(nn));//外面留下最大值
}
}
else if(y == 1){//直接把小的扔进去，外面留一个最大值
for(i = qs;i <= n;++i){
int sz = i <= mx ? p[i].size() : 0;
sl += sz;
if(sl <= 1){sl = 0;continue;}
for(j = 0;j < p[i].size();++j){
tot += p[i][j];
ss.insert(p[i][j]);
}
mm = *ss.begin();//当前最小值
nn = *ss.rbegin();//当前最大值
ans += tot - nn;//这一层的权值是sum-mx
--sl;tot -= nn;ss.erase(ss.find(nn));//外面留下最大值
}
}
else if(x == 1){//两种贪心取最优
ans = wk(qs); //贪心1：把全局最大值放进最里层
//贪心2：如果开局是2 1 1...1 k结构，把前面这些层的最小值放进k这一层，后续不变
int o;for(o = qs + 1;o <= mx;++o) if(p[o].size() != 1) break;
if(p[qs].size() == 2){//只有全局最大出现在前半段时可能会有影响
tot = 0;mm = 1e9;
for(i = qs;i < o;++i){
for(j = 0;j < p[i].size();++j){
tot += p[i][j];
mm = min(mm,p[i][j]);
}
}
ss.insert(mm);
li an = wk(o);
ans = min(ans,an + tot - mm);
}
}
print(ans);pc('\n');
return 0;
}
d2t3：
#include<bits/stdc++.h>
#define gc getchar()
#define pc putchar
#define li long long
#define mp make_pair
#define pli pair<li,int>
#define fi first
#define se second
#define pb push_back
using namespace std;
inline li read(){
li x = 0;
int y = 0,c = gc;
while(c < '0' || c > '9') y = c,c = gc;
while(c >= '0' && c <= '9') x = x * 10 + c - '0',c = gc;
return y == '-' ? -x : x;
}
inline void prt(li x){
if(x >= 10) prt(x / 10);
pc(x % 10 + '0');
}
inline void print(li x){
if(x < 0) pc('-'),x = -x;
prt(x);
}
inline void file(char *s){
char c[50];
sprintf(c,"%s.in",s);
freopen(c,"r",stdin);
sprintf(c,"%s.out",s);
freopen(c,"w",stdout);
}
int n;
#define M 5005
li a[M];
int fa[M],ls[M],rs[M];
vector<li> f[M][M];
vector<int> ch[M];
int dpt[M];
bool inzs[M][M];
li vl[M],vr[M],dl[M],dr[M];
pli xl[M];
inline li operator * (pli x,pli y){
return x.fi * y.se - x.se * y.fi;
}
inline li operator * (pli x,li y){
return x.se * y + x.fi;
}
inline pli operator - (pli x,pli y){
return mp(x.fi - y.fi,x.se - y.se);
}
void dfs(int x){
if(!x) return;
int lc = ls[x],rc = rs[x];
dfs(lc);dfs(rc);
dpt[x] = max(dpt[lc],dpt[rc]) + 1;
int i = 0,j = 0,k,l,o,p,q,d,dt = dpt[x];
li ax = a[x];
ch[x].pb(x);
int szl = ch[lc].size(),szr = ch[rc].size();
while(i < szl && j < szr){
if(a[ch[lc][i]] < a[ch[rc][j]]) ch[x].pb(ch[lc][i++]);
else ch[x].pb(ch[rc][j++]);
}
while(i < szl) ch[x].pb(ch[lc][i++]);
while(j < szr) ch[x].pb(ch[rc][j++]);
for(i = 1;i < ch[x].size() && ax > a[ch[x][i]];++i) swap(ch[x][i - 1],ch[x][i]);
for(i = 0;i < ch[x].size();++i) inzs[x][ch[x][i]] = 1;
if(!lc) f[x][x].pb(ax);
if(lc && !rc){
f[x][x].resize(dt);
for(d = 0;d < dt;++d) f[x][x][d] = 1e18l;
for(i = 0;i < szl;++i){
p = ch[lc][i];
for(d = 1;d <= f[lc][p].size();++d){
f[x][x][d] = min(f[x][x][d],f[lc][p][d - 1] + ax);
}
}
for(i = 0;i < szl;++i){
p = ch[lc][i];
f[x][p].pb(1e18l);
for(d = 0;d < f[lc][p].size();++d){
f[x][p][0] = min(f[x][p][0],f[lc][p][d] + ax * (d + 1) + a[p]);
}
}
}
if(rc){
memset(vl,0x1f,sizeof(vl));
memset(vr,0x1f,sizeof(vr));
memset(dl,0x1f,sizeof(dl));
memset(dr,0x1f,sizeof(dr));
for(i = 0;i < szl;++i){
p = ch[lc][i];
for(d = 0;d < f[lc][p].size();++d){
vl[p] = min(vl[p],f[lc][p][d] + ax * (d + 1));
dl[d] = min(dl[d],f[lc][p][d]);
}
}
for(j = 0;j < szr;++j){
q = ch[rc][j];
for(d = 0;d < f[rc][q].size();++d){
vr[q] = min(vr[q],f[rc][q][d] + ax * (d + 1));
dr[d] = min(dr[d],f[rc][q][d]);
}
}
f[x][x].resize(dt);
for(d = 0;d < dt;++d) f[x][x][d] = 1e18l;
for(i = 0;i < szl;++i){
p = ch[lc][i];
li tmp = 1e18l;
for(o = 0;o < dpt[rc];++o) tmp = min(tmp,dr[o] + a[p] * (o + 1));
for(d = 1;d <= f[lc][p].size();++d){
f[x][x][d] = min(f[x][x][d],f[lc][p][d - 1] + tmp + a[x]);
}
}
for(j = 0;j < szr;++j){
q = ch[rc][j];
li tmp = 1e18l;
for(o = 0;o < dpt[lc];++o) tmp = min(tmp,dl[o] + a[q] * (o + 1));
for(d = 1;d <= f[rc][q].size();++d){
f[x][x][d] = min(f[x][x][d],f[rc][q][d - 1] + tmp + a[x]);
}
}
for(i = 0;i < szl;++i){
p = ch[lc][i];
f[x][p].resize(dpt[rc] + 1);
f[x][p][0] = 1e18l;
for(d = 1;d <= dpt[rc];++d){
f[x][p][d] = vl[p] + dr[d - 1] + a[p];
}
int sl = 0;
for(o = 0;o < f[lc][p].size();++o) if(f[lc][p][o] <= 3e14l){
pli nxt = mp(f[lc][p][o],o + 1);
while(sl >= 2 && (nxt - xl[sl]) * (xl[sl - 1] - xl[sl]) >= 0) --sl;
xl[++sl] = nxt;
}
for(j = 0,o = sl;j < szr;++j){
q = ch[rc][j];
while(o > 1 && xl[o] * a[q] >= xl[o - 1] * a[q]) --o;
if(o) f[x][p][0] = min(f[x][p][0],vr[q] + xl[o] * a[q] + a[p]);
}
}
for(j = 0;j < szr;++j){
q = ch[rc][j];
f[x][q].resize(dpt[lc] + 1);
f[x][q][0] = 1e18l;
for(d = 1;d <= dpt[lc];++d){
f[x][q][d] = vr[q] + dl[d - 1] + a[q];
}
int sl = 0;
for(o = 0;o < f[rc][q].size();++o) if(f[rc][q][o] <= 3e14l){
pli nxt = mp(f[rc][q][o],o + 1);
while(sl >= 2 && (nxt - xl[sl]) * (xl[sl - 1] - xl[sl]) >= 0) --sl;
xl[++sl] = nxt;
}
for(i = 0,o = sl;i < szl;++i){
p = ch[lc][i];
while(o > 1 && xl[o] * a[p] >= xl[o - 1] * a[p]) --o;
if(o) f[x][q][0] = min(f[x][q][0],vl[p] + xl[o] * a[p] + a[q]);
}
}
}
}
int main(){
//file("mis");
int i,k;
n = read();
for(i = 1;i <= n;++i) a[i] = read();
for(i = 2;i <= n;++i){
k = read();fa[i] = k;
if(ls[k]) rs[k] = i;
else ls[k] = i;
}
dfs(1);
li ans = 1e18l;
for(i = 0;i < dpt[1];++i) ans = min(ans,f[1][1][i] + a[1] * (i - 1));
print(ans);pc('\n');
return 0;
}
