蜜月日记 Part10

littlez_meow · 2025-02-01 21:46:05 · 休闲·娱乐

前言

Day 100 最后冲刺！

Day 91

由于原本这一天的题过于简单了且没有技巧所以换掉。

神秘线代科技。

2025/06/30 [PA 2022] Drzewa rozpinające

题意

给定一个长为 n 的序列 a_1,\cdots,a_n。有 n 个点，第 i 个点和第 j 个点之间连了 \gcd(a_i,a_j) 条边，求这张图的生成树个数对 10^9+7 取模的值。

思路

设值域为 m。

先回忆一下无向图矩阵树定理。设 D 为度数矩阵去掉最后一行最后一列，G 为邻接矩阵去掉最后一行最后一列，则生成树个数为 \det(D-G)。

直接计算就 O(n^3) 了显然是跑不过的。我们需要用行列式的性质化简。

事实上，我们有：

【矩阵行列式引理】 对于 n\times n 的可逆矩阵 A 和 n\times m 的矩阵 U,V，有 \det(A+UV^{\top})=\det A\det(I+V^{\top}A^{-1}U)。

如果 A 的行列式好算（比如对角矩阵），且 \det(I+V^{\top}A^{-1}U) 更好算（比如 m<<n 时）可以用矩阵行列式引理来算。

回到矩阵树定理。发现这个定理的形式就是给我们用这个的。我们要求 \det(D-G)，其中 D 是对角矩阵行列式好算，只需要找到合适的 U,V 即可。

观察 G 的结构，我们有 G_{i,j}=\gcd(a_i,a_j)=\sum\limits_{d|a_i,d|a_j}\varphi(d)=\sum\limits_{d=1}^m[d|a_i]\varphi(d)[d|a_j]。

于是构造 (n-1)\times m 的矩阵 U,V，其中 U_{i,d}=[d|a_i]\varphi(d),V_{i,d}=[d|a_j]，则 G=UV^{\top}。

那么 (I-V^{\top}D^{-1}U)_{i,j}=[i=j]-\varphi(j)\sum\limits_{t=1}^{n-1}[i|a_t][j|a_t]。这个只在 \operatorname{lcm}(i,j)\le m 的时候有值。

每次只消元有值的位置，复杂度能过。不能过把矩阵转置一下就过了。

代码

#include<bits/stdc++.h>
#define F(i,a,b) for(int i(a),i##i##end(b);i<=i##i##end;++i)
#define R(i,a,b) for(int i(a),i##i##end(b);i>=i##i##end;--i)
#define ll long long
#define File(a) freopen(#a".in","r",stdin);freopen(#a".out","w",stdout)
using namespace std;
const int MAXN=5001,MOD=1e9+7;
inline ll qpow(ll b,int e){ll res=1;while(e)(e&1)&&(res=res*b%MOD),b=b*b%MOD,e>>=1;return res;}
int n,m,a[MAXN];
int vis[MAXN],phi[MAXN];
vector<int>pr;
inline void init(){
    phi[1]=1;
    F(i,2,m){
        if(!vis[i]) vis[i]=i,phi[i]=i-1,pr.emplace_back(i);
        for(int j:pr){
            int k=i*j;
            if(k>m) break;
            vis[k]=j;
            if(vis[i]==j){phi[k]=phi[i]*j;break;}
            else phi[k]=phi[i]*(j-1);
        }
    }
}
int D[MAXN],G[MAXN][MAXN];
inline ll det(){
    bool inv=0;
    ll res=1;
    F(i,1,m){
        int t=-1;
        F(j,i,m) if(G[j][i]){t=j;break;}
        if(t==-1) return 0;
        if(t!=i) swap(G[t],G[i]),inv^=1;
        res=res*G[i][i]%MOD;
        vector<int>pos;
        F(j,i,m) if(G[i][j]) pos.emplace_back(j);
        ll inv=qpow(MOD-G[i][i],MOD-2)%MOD;
        F(j,i+1,m) if(G[j][i]){
            ll coef=G[j][i]*inv%MOD;
            for(int k:pos) G[j][k]=(G[j][k]+G[i][k]*coef)%MOD;
        }
    }
    return inv?MOD-res:res;
}
signed main(){ 
    ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);
    cin>>n;
    F(i,1,n) cin>>a[i],m=max(m,a[i]);
    init();
    F(i,1,n) F(j,1,n) D[i]+=__gcd(a[i],a[j]);
    ll coef=1;
    F(i,1,n-1) coef=coef*D[i]%MOD,D[i]=qpow(D[i],MOD-2);
    F(i,1,m) F(j,1,m) if(i*j/__gcd(i,j)<=m){
        ll qwq=0;
        F(k,1,n-1) if(a[k]%i==0&&a[k]%j==0) (qwq+=D[k])>=MOD&&(qwq-=MOD);
        (G[m-i+1][m-j+1]=((i==j)-phi[j]*qwq)%MOD)<0&&(G[m-i+1][m-j+1]+=MOD);
    }
    cout<<coef*det()%MOD;
    return 0;
}

Day 92

生成子群相关完全不会啊。

2025/02/03 [PA 2024] Grupa permutacji

题意

给定 k 个长为 n 的置换，求它们生成子群的逆序对的平均数对 10^9+7 取模的值。

思路

生成子群最重要的性质是，假设这个生成子群的所有置换中的第 i 位有 k 种取值，那么每种取值的置换个数相同。

这个性质的推论是，选出若干位组成一个向量，这个向量的每种取值对应的置换个数也是相等的。

在本题中，我们可以考虑对所有 i\neq j 的二元组 (i,j) 建点，(i,j) 和所有 (p_i,p_j) 连双向边，则一个连通块中的所有元素就是这两位可能的值。维护连通块中 i<j 和 i>j 的点数，设分别为 a,b，则贡献为 \dfrac{ab}{a+b}。

直接维护是 O(n^2k) 的，跑不过去。

前面的 O(n^2) 基本上没法再优化了。我们试图优化一下 O(k)。

有一个确定性做法是 Schreier–Sims 算法，但是我不会。你感觉一下，我们随机选出 O(\log n) 个给出置换的子集复合起来，得到的所有置换大概率覆盖了所有上面图的边。

所以复杂度变成了 O(n(n+k)\log n)。

代码

#include<bits/stdc++.h>
#define File(a) freopen(#a".in","r",stdin);freopen(#a".out","w",stdout)
#define ll long long
#define F(i,a,b) for(int i(a),i##i##end(b);i<=i##i##end;++i)
#define R(i,a,b) for(int i(a),i##i##end(b);i>=i##i##end;--i)
using namespace std;
const int MAXN=3001,MOD=1e9+7;
int n,k,a[MAXN][MAXN],dsu[MAXN*MAXN];
inline int id(int i,int j){
    return (i-1)*n+j;
}
int find(int x){
    return x==dsu[x]?x:dsu[x]=find(dsu[x]);
}
mt19937 gen(time(0)^*new int);
ll le[MAXN*MAXN],ge[MAXN*MAXN];
inline ll qpow(ll base,int expo=MOD-2){
    ll res=1;
    while(expo){
        (expo&1)&&(res=res*base%MOD);
        base=base*base%MOD,expo>>=1;
    }
    return res;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>k;
    F(i,1,k) F(j,1,n) cin>>a[i][j];
    iota(dsu+1,dsu+n*n+1,1);
    F(T,1,40){
        static int p[MAXN],pp[MAXN];
        iota(p+1,p+n+1,1);
        F(i,1,k) if(gen()&1){
            F(j,1,n) pp[p[j]]=a[i][j];
            swap(p,pp);
        }
        F(i,1,n) F(j,1,n) if(i!=j) dsu[find(id(p[i],p[j]))]=find(id(i,j));
    }
    F(i,1,n) F(j,1,n) if(i!=j){
        if(i<j) ++le[find(id(i,j))];
        else ++ge[find(id(i,j))];
    }
    int ans=0;
    F(i,1,n) F(j,1,n) if(i!=j&&find(id(i,j))==id(i,j)) ans=(ans+le[id(i,j)]*ge[id(i,j)]%MOD*qpow(le[id(i,j)]+ge[id(i,j)]))%MOD;
    cout<<ans;
    return 0;
}

Day 93

太久没写了，随便找了一道，结果是金牌题……

和数学过情人节。

2025/02/14 [AGC063F] Simultaneous Floor

题意

求把 (a_1,a_2) 变成 (b_1,b_2) 的最小操作次数，一次操作定义为选择一个正实数 x，执行 (a_1,a_2)\leftarrow (\lfloor a_1x\rfloor,\lfloor a_2x\rfloor)，或报告无解。

思路

把有序数对看成坐标，扔到平面直角坐标系上研究。下面记点 A(a_1,a_2),B(b_1,b_2)。不加说明时，我们均指第一象限。记值域为 V。

发现点 P(x,y) 可以变成形如 (i,\lfloor\dfrac{y}{x}i\rfloor),(\lfloor\dfrac {x}{y}i\rfloor,i),i\in\mathbb Z 的点。不过还是有向下取整，不好描述。

那么倒过来看，对于 Q(p,q)，能够到达它的 P 的集合是什么。

设直线 OP:y=kx，如果 P 能到达 Q，则 OP 必须穿过以 Q 为左下角、边长为 1 的正方形，穿过是指 OP 在正方形内的部分的长度 >0。

设 Q_u(p,q+1),Q_r(p+1,q)，则只要 OP 在 \angle Q_rOQ_u 内部（不包括 OQ_u,OQ_r），其就会穿过这个正方形。

那么就有 k\in(k_{OQ_r},k_{OQ_u})，即能够到达 Q(p,q) 的 P\in\{(x,y)|\dfrac{q}{p+1}<\dfrac y x<\dfrac{q+1}p\}。

设 l_1=\dfrac{b_2}{b_1+1},r_1=\dfrac{b_2+1}{b_1}，我们就可以算出经过 \le 1 次操作到达 B 的点的集合为 S_1=\{(x,y)|l_1<\dfrac y x<r_1\}。

同理，设 l_2=\min\{\dfrac y{x+1}|(x,y)\in S_1\},r_2=\max\{\dfrac{y+1}x|(x,y)\in S_1\}，则经过 \le 2 次操作到达 B 的点的集合为 S_2=\{(x,y)|l_2<\dfrac y x<r_2\}。

更一般地，对于 t\ge 2，设 l_t=\min\{\dfrac y{x+1}|(x,y)\in S_{t-1}\},r_t=\max\{\dfrac{y+1}x|(x,y)\in S_{t-1}\}，则经过 \le t 次操作到达 B 的点的集合为 S_t=\{(x,y)|l_t<\dfrac y x<r_t\}。

先来研究已知 l_{t-1},r_{t-1} 如何求 l_t,r_t。下面只讨论 l_t，r_t 是类似的。

问题相当于求最小的 \dfrac{y}{x+1}，满足 l_{t-1}<\dfrac{y}{x}<r_{t-1}。考虑到 \dfrac{y}{x+1}=\dfrac{1}{\frac{x}{y}+\frac{1}{y}}，即我们要 y 尽量小 \dfrac{x}{y} 尽量大。在 y 最小的同时取 x 最大即可，可以用反证法和一些缩放证明。

同理，求 r_t 时找满足 x 最小的最大 y 即可。

找到这样的 x,y 可以在 SBT 上二分实现。

接下来就是要求第一次满足 A\in S_t 的 t。打表发现 l_t,r_t 在迭代若干轮之后就不变了，所以可以暴力求每一轮的 l_t,r_t 是多少。考虑到 l,r 在 SBT 上移动的过程，得到 x=1 或 y=1 后就不会变了，所以迭代次数是 O(\log V) 的。

注意有点在坐标轴、y=x 上以及不在 y=x 同一侧的时候判无解。可以用关于 y=x 对称简化讨论。

总的复杂度是 O(T\log^2 V)。

代码

#include<bits/stdc++.h>
#define File(a) freopen(#a".in","r",stdin);freopen(#a".out","w",stdout)
#define ll long long
#define F(i,a,b) for(int i(a),i##i##end(b);i<=i##i##end;++i)
#define R(i,a,b) for(int i(a),i##i##end(b);i>=i##i##end;--i)
using namespace std;
struct Frac{
    ll x,y;
    Frac(const ll&a=0,const ll&b=0):x(a),y(b){}
    inline void reduce(){ll qwq=__gcd(x,y);x/=qwq,y/=qwq;}
    inline Frac inv(){return Frac(y,x);}
    bool operator<(const Frac&qwq)const{return x*qwq.y<y*qwq.x;}
    bool operator==(const Frac&qwq)const{return x==qwq.x&&y==qwq.y;}
};
Frac find(Frac ql,Frac qr){
    Frac l=Frac(0,1),r=Frac(1,0),now=Frac(1,1);
    while(!(ql<now&&now<qr)){
        if(!(ql<now)){
            ll fac=(ql.x*now.y-ql.y*now.x)/(ql.y*r.x-ql.x*r.y)+1;
            now=Frac(now.x+fac*r.x,now.y+fac*r.y),l=Frac(now.x-r.x,now.y-r.y);
        }else{
            ll fac=(qr.y*now.x-qr.x*now.y)/(qr.x*l.y-qr.y*l.x)+1;
            now=Frac(now.x+fac*l.x,now.y+fac*l.y),r=Frac(now.x-l.x,now.y-l.y);
        }
    }
    if(now.y==1) now.x=(qr.x-1)/qr.y;
    now.reduce();
    return now;
}
ll a1,a2,b1,b2;
inline int solve(){
    if(a1>a2) swap(a1,a2),swap(b1,b2);
    Frac a=Frac(a1,a2),b=Frac(b1,b2);
    if(a==b) return 0;
    if(!a1&&!a2) return -1;
    if(!a1) return b1?-1:1;
    if(!b1&&!b2) return 1;
    if(a1==a2) return b1==b2?1:-1;
    if(b1>b2) return -1;
    if(!b1) return 1+(a2<=a1*b2);
    Frac l(b1,b2+1),r(b1+1,b2);
    l.reduce(),r.reduce(),a.reduce();
    if(Frac(1,b2/b1+1)<a){
        int t=1;
        while(!(l<a&&a<r)){
            ++t;
            Frac nl=l.x>1?find(r.inv(),l.inv()).inv():Frac(l.x,l.y-1),nr=r.y>1?find(l,r):Frac(r.x-1,r.y);
            l=nl,r=nr;
            ++l.y,++r.x;
            l.reduce(),r.reduce();
        }
        return t;
    }
    return -1;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int T;
    for(cin>>T;T;--T){
        cin>>a1>>a2>>b1>>b2;
        cout<<solve()<<"\n";
    }
    return 0;
}

Day 94

看过的没写代码的题，回旋镖正中靶心。

2025/02/19 『JROI-4』少女幻葬

题意

给定 n,k，求有多少个长为 n 的序列 a_1,\cdots,a_n，满足 l_i\le a_i\le r_i,\gcd(a_i,a_{i+1})\neq k,\gcd(a_i,a_{i+1},a_{i+2})=k。

思路

记值域为 m。

由于 \gcd(a_i,a_{i+1},a_{i+2})=k，所以有 k|a_i。不妨令 a_i\leftarrow\dfrac{a_i}{k},l_i\leftarrow\lceil\dfrac{l_i}{k}\rceil,r_i\leftarrow\lfloor\dfrac{r_i}{k}\rfloor。则原限制转化为 l_i\le a_i\le r_i,\gcd(a_i,a_{i+1})\neq 1,\gcd(a_i,a_{i+1},a_{i+2})=1。接下来的 k 和题目里的没有关系。

设一个状态转移会比较抽象。设 f(i,j,k) 表示考虑到第 i 个数，a_i=k，\gcd(a_i,a_{i-1})=j 的方案数；设 g(i,j,k) 表示考虑到第 i 个数，a_i=k，\gcd(a_i,a_{i+1})=j 的方案数。

首先是 g 到 f 的转移为 f(i,j,k)=\sum\limits_{v=l_{i-1}}^{r_{i-1}}g(i-1,j,v)[\gcd(v,k)=j]。

除掉 j 后反演得到 f(i,j,k)=\sum\limits_{v=\lceil\frac{l_{i-1}}{j}\rceil}^{\lfloor\frac{r_{i-1}}{j}\rfloor}g(i-1,j,vj)\sum\limits_{d|v,d|\frac{k}{j}}\mu(d)。

即：

不妨 k\leftarrow \dfrac k j，对第三维做狄利克雷后缀和，对位乘 \mu 后再做狄利克雷前缀和即可转移，时间复杂度 O(nm\log m\log\log m)，前一个 \log m 是枚举因数的调和级数，后一个 \log\log m 是狄利克雷前后缀和。

然后再是 f 到 g 的转移为：

枚举 k，把 f(i,x,k) 贡献到 x 的质因数集合的位置然后求高维后缀和，那么 g(i,j,k) 就是 j 的质因数集合的补集的位置。这一部分复杂度是 \sum\limits_{k\le m}d(k)\omega(k)=\sum\limits_{k\le m}\omega(k)\sum\limits_{i|k}1=\sum\limits_{ik\le m}\omega(ik)\le\sum\limits_{ik\le m}(\omega(i)+\omega(k))=2\sum\limits_{i\le m}\sum\limits_{k\le\frac m i}\omega(i)=2\sum\limits_{i\le m}O(\dfrac m i\log\log\dfrac v i)=O(m\log m\log\log m)。加上枚举第一维，总的复杂度是 O(nm\log m\log\log m)。

然后就做完了，时间复杂度 O(nm\log m\log\log m)。

代码

#include<bits/stdc++.h>
#define File(a) freopen(#a".in","r",stdin);freopen(#a".out","w",stdout)
#define ll long long
#define F(i,a,b) for(int i(a),i##i##end(b);i<=i##i##end;++i)
#define R(i,a,b) for(int i(a),i##i##end(b);i>=i##i##end;--i)
using namespace std;
const int MAXN=2001,MAXV=5001,MOD=998244353;
inline void add(int&x,int y){(x+=y)>=MOD&&(x-=MOD);}
int n,m,l[MAXN],r[MAXN],tot;
int pr[MAXV],cnt,vis[MAXV],mu[MAXV],omega[MAXV];
inline void init(){
    mu[1]=1;
    F(i,2,m){
        !vis[i]&&(pr[++cnt]=i,vis[i]=i,mu[i]=-1);
        F(j,1,cnt){
            int t=i*pr[j];
            if(t>m) break;
            vis[t]=pr[j];
            if(vis[i]==pr[j]) break;
            else mu[t]=-mu[i];
        }
    }
    return;
}
vector<int>fac[MAXV];
int id[MAXV][MAXV];
int f[50000],g[50000],tmp[50000],pf[50000];
int sum[130];
signed main(){ 
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int k=0;
    cin>>n>>k;
    F(i,1,n) cin>>l[i]>>r[i],l[i]=(l[i]-1)/k+1,r[i]=r[i]/k,m=max(m,r[i]);
    init();
    F(i,1,m) for(int j=i;j<=m;j+=i) fac[j].push_back(i),id[j][i]=++tot;
    F(i,2,m){
        static int idx[MAXV];
        int now=0,qwq=i,qaq=-1;
        while(qwq!=1){
            if(now!=vis[qwq]) now=vis[qwq],idx[now]=++qaq;
            qwq/=vis[qwq];
        }
        omega[i]=qaq+1;
        for(int j:fac[i]){
            qwq=j;
            while(qwq!=1) pf[id[i][j]]|=(1<<idx[vis[qwq]]),qwq/=vis[qwq];
        }
    }
    F(i,2,m) for(int j=((l[1]-1)/i+1)*i;j<=r[1];j+=i) g[id[j][i]]=1;
    F(i,2,n){
        F(j,2,m){
            for(int k=j,qwq=1;k<=m;k+=j,++qwq) tmp[qwq]=g[id[k][j]];
            int lim=m/j;
            F(k,1,cnt){
                if(pr[k]>lim) break;
                for(int t=lim/pr[k]*pr[k];t>=pr[k];t-=pr[k]) add(tmp[t/pr[k]],tmp[t]);
            }
            F(k,1,lim) (tmp[k]=tmp[k]*mu[k])<0&&(tmp[k]+=MOD);
            F(k,1,cnt){
                if(pr[k]>lim) break;
                for(int t=pr[k];t<=lim;t+=pr[k]) add(tmp[t],tmp[t/pr[k]]);
            }
            for(int k=j,qwq=1;k<=m;k+=j,++qwq) f[id[k][j]]=tmp[qwq];
        }
        F(j,2,m) for(int k=j;k<=m;k+=j) if(k<l[i]||k>r[i]) f[id[k][j]]=0;
        F(k,2,m){
            F(j,0,(1<<omega[k])-1) sum[j]=0;
            for(int j:fac[k]) if(j!=1) add(sum[pf[id[k][j]]],f[id[k][j]]);
            F(j,0,omega[k]-1) F(s,0,(1<<omega[k])-1) if(s>>j&1) add(sum[s],sum[s^(1<<j)]);
            for(int j:fac[k]) if(j!=1) g[id[k][j]]=sum[((1<<omega[k])-1)^pf[id[k][j]]];
        }
    }
    int ans=0;
    F(i,2,m) for(int j=i;j<=m;j+=i) add(ans,f[id[j][i]]);
    cout<<ans;
    return 0;
}

Day 95

一个很厉害的技巧。

2025/02/22 [ABC311Ex] Many Illumination Plans

题意

有一个以 1 为根的有 n 个节点的树，每一个点有权值值 B_i、重量 W_i 和颜色 C_i\in\{0,1\}。要求对于每一个点 u 的子树 T_u 回答以下问题：

可以对 T_u 进行若干次操作，每一次选择一个非根节点，将这个点的所有儿子转移给其父亲，然后删去该节点。操作后应满足 T_u 中不存在两端点同色的边，所有点的重量和小于 X。问操作之后的 T_u 的权值之和的最大值。

思路

先讨论求以 1 为根子树的答案。

删除顺序是不重要的，所以可以当成选几个点满足重量和 \le X、与选中的点里最近的祖先颜色不同，使得权值和最大。也就是背包。

于是设 dp(i,j,k) 表示当前在节点 i 子树中、重量和为 j、最浅的点的颜色为 k 的最大权值和，转移为对于 u 的儿子 v 把 dp(u,*,C_u) 为 dp(u,*,C_u) 和 dp(v,*,1-C_u) 的 \max 卷积。

然后你发现完蛋了，\max 卷积是 O(X^2) 的。但是一个插入数是 O(X) 的，我们只要想办法把 \max 卷积变成插入一个数就好了。

怎么办呢？你发现 \max 卷积具有交换律和结合律，所以我们可以随便改变运算顺序。再加上每次我们初始的时候 dp 数组都为空，这个很浪费。不如每次递归子树时传入现在的“半成品”dp 数组，回溯的时候把当前节点的贡献再加进去。由于 k 有两种取值，我们要 dfs 两次子树，每个点被访问了 O(\text{祖先个数次})，总的复杂度变成了 O(n^2X)。已经比 O(nX^2) 好了！

在下一步我们使用多次递归子树的经典 Trick：轻重子树分治。你考虑第一次递归进去的时候 dp(u,*,0),dp(u,*,1) 都是 \max 卷积的幺元，这两个没有区分，只需要递归一次。所以先递归一次重儿子，轻儿子再递归两次。

分析一下复杂度。设 n 个点的树复杂度为 T(n)，重儿子子树大小为 h，其他子树大小为 y_1,\cdots,y_t，则 T(n)=T(h)+O(C)+2\sum\limits_{i=1}^t T(y_i)。显然复杂度高于 O(n)，此时根据调整法取 y_1=n-1-h,y_2=\cdots=y_t=0 取到最大 T(h)+2T(n-1-h)。进一步，由于 n-1-h\le h，取 h=\dfrac{n-1}{2} 最优，即 T(n)\le 3T(\dfrac n 2)+O(C)。根据主定理，得到复杂度上界 O(n^{\log_2 3}C)。

然后是对每个子树求。你发现上面这个东西一次求了一条重链的答案，所以再遍历一遍轻子树即可，复杂度仍然是 O(n^{\log_2 3}C)，其中 \log_2 3\approx 1.582。

代码

#include<bits/stdc++.h>
#define File(a) freopen(#a".in","r",stdin);freopen(#a".out","w",stdout)
#define ll long long
#define F(i,a,b) for(int i(a),i##i##end(b);i<=i##i##end;++i)
#define R(i,a,b) for(int i(a),i##i##end(b);i>=i##i##end;--i)
#define poly vector<ll>
#define fi first
#define se second
using namespace std;
const int MAXN=201,MAXV=50001;
int n,X,W[MAXN],C[MAXN],fa[MAXN],siz[MAXN],son[MAXN];
ll ans[MAXN],B[MAXN];
vector<int>g[MAXN];
void dfs1(int now){
    siz[now]=1;
    for(int i:g[now]) dfs1(i),siz[now]+=siz[i],siz[son[now]]<siz[i]&&(son[now]=i);
    return;
}
poly zero;
vector<poly> dfs2(int now,poly dp,bool heavy){
    if(!heavy) for(int i:g[now]) if(i!=son[now]) dfs2(i,dp,0);
    vector<poly>qwq(2,zero);
    if(son[now]){
        qwq=dfs2(son[now],dp,heavy);
        for(int i:g[now]) if(i!=son[now]) F(j,0,1) qwq[j]=dfs2(i,qwq[j],1)[j];
    }else qwq[0]=qwq[1]=dp;
    R(i,X,W[now]){
        qwq[C[now]][i]=max(qwq[C[now]][i],qwq[C[now]^1][i-W[now]]+B[now]);
        if(!heavy) ans[now]=max(ans[now],qwq[C[now]^1][i-W[now]]+B[now]);
    }
    return qwq;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>X;
    F(i,2,n) cin>>fa[i],g[fa[i]].push_back(i);
    F(i,1,n) cin>>B[i]>>W[i]>>C[i];
    dfs1(1);
    zero=poly(X+1,-5e17);
    zero[0]=0;
    dfs2(1,zero,0);
    F(i,1,n) cout<<ans[i]<<"\n";
    return 0;
}

Day 96

五合一。

2025/02/24 [CEOI 2020] 象棋世界

题意

在 r 行 c 列的棋盘上，q 组询问兵、车、后、象、王从 (1,c_1) 到 (r,c_r) 的最小步数和达到最小步数的方案数，或判断到达不了。保证 r\ge c。

思路

兵