2024 4月杂题
归来！
QOJ# 6842. Popcount Words
题意：
- 定义 $s_i = \mathrm{popcount}(i) \bmod 2, w(l, r) = s_ls_{l+1}\dots s_r$（此处表示字符串连接）。
- 给出若干区间 $[l_i,r_i]$，令 $S = w(l_1, r_1) + w(l_2, r_2) + \dots + w(l_n, r_n)$（此处加号表示字符串连接）。
- $q$ 次询问一个串 $T$ 在 $S$ 中的出现次数。
- $n,q \le 10^5, 1 \le l_i \le r_i \le 10^9,\sum|T| ≤ 5 × 10^5$
题解
首先不看数据范围，容易想到把 $T$ 塞到 AC 自动机里面然后直接跑 $S$。
再看一眼数据范围，哇塞 $|S|\le 10^5\times 10^9$，显然是不行的。
难道就没办法了吗？容易看到有一个 $\mathrm{popcount}$，这个容易让人往二进制方面想。那么考虑 $2^k$ 在题目条件下有无特殊性质。
容易想到 $2^k\sim 2^{k+1}-1$ 恰好是 $0\sim 2^k-1$ 每个数再在最高位加一个 $1$，也就是说 $w(0,2^k-1)$ 与 $w(2^k,2^{k+1}-1)$ 每个数 $\mathrm{popcount}$ 的奇偶性恰好是完全相反的关系！这就说明对应字符串也是相反关系。
这启发我们使用倍增求解。具体来说，对 AC 自动机上每个点 $i$ 求出 $f_{i,j,0/1}$ 表示“从 $i$ 开始，经过 $w(0,2^j-1)$（$0/1$ 表示反转的版本）后将到达哪个点”。这个预处理是简单的，不做赘述。并且注意到可以将任何一对 $[l_i,r_i]$ 分成若干段 $2$ 的整数次幂后转化为 $w(0,2^k)$ 或其反转（类似于线段树把任何一个区间划分成 $\log n$ 段）。对于统计答案，可以先存每个 $f_{i,j,0/1}$ 被用过几次（注意端点问题），然后从大到小倍增将答案统计到点上。
但是这个倍增没有 $\mathrm{lca}$ 那么好做，因为必须找到某个区间 $[l_i,r_i]$ 中 $2$ 的整数次幂才能做，怎么办呢？仍然用线段树的思路，注意到 zkw 线段树的某个结点恰好是一个 $w(p,p+2^k-1)$，其中 $p$ 是一个“必定存在非负整数 $\lambda$，使得 $p=\lambda2^k$” 的数。也就是说直接算出 $p$ 的 $\mathrm{popcount}(p)$ 就能知道将 $w(p,p+2^k-1)$ 转化为 $w(0,2^k-1)$ 是否需要反转。而知道左右端点后是很好求出对应区间在 zkw 线段树上所有结点编号的。现在的问题就是如何从 zkw 的结点编号推出区间左右端点。
设 zkw 线段树对应序列长度为 $2^k$（即下标区间为 $[0,2^k)$），容易发现结点 $t$ 的长度为 $2^{k-\mathrm{highbit}(t)}$，并且 $t-2^{\mathrm{highbit}(t)}$ 恰好是 $t$ 是它在对应层数的第多少块，即它的左右端点分别是 $2^{k-\mathrm{highbit}(t)}\times (t-2^{\mathrm{highbit}(t)})$ 和 $2^{k-\mathrm{highbit}(t)}\times (t-2^{\mathrm{highbit}(t)}+1)-1$，然后就做完了。
复杂度 $O(\sum T+n\log V)$。
参考代码
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define forup(i,s,e) for(int i=(s);i<=(e);i++)
#define fordown(i,s,e) for(int i=(s);i>=(e);i--)
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void()
#endif
using namespace std;
using pii=pair<int,int>;
using i64=long long;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
inline int read(){
int x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int N=5e5+5,inf=0x3f3f3f3f,M=1<<30;
int n,q,len,ed[N];
i64 sum[N];
char t[N];
vector<pii> ss;
int ppcnt(int x){
int res=0;
while(x){
x-=x&-x;
++res;
}
return res;
}
int hbt(int x){
fordown(i,30,0){
if(x>>i) return i;
}
return -1;
}
struct AC_automaton{
int tr[N][2],cntn,fail[N],f[N][31][2];
i64 cnt[N][31][2];
vector<int> e[N];
void Insert(char* t,int len,int num){
int p=0;
forup(i,1,len){
int c=t[i]-'0';
if(!tr[p][c]) tr[p][c]=++cntn;
p=tr[p][c];
}
ed[num]=p;
}
void Build(){
queue<int> q;
forup(i,0,1){
if(tr[0][i]){
fail[tr[0][i]]=0;
q.push(tr[0][i]);
}
}
while(q.size()){
int u=q.front();q.pop();
forup(i,0,1){
if(tr[u][i]){
fail[tr[u][i]]=tr[fail[u]][i];
q.push(tr[u][i]);
}else{
tr[u][i]=tr[fail[u]][i];
}
}
}
forup(i,1,cntn){
e[fail[i]].push_back(i);
}
forup(i,0,cntn){
f[i][0][0]=tr[i][0];
f[i][0][1]=tr[i][1];
}
forup(i,1,30){
forup(j,0,cntn){
f[j][i][0]=f[f[j][i-1][0]][i-1][1];
f[j][i][1]=f[f[j][i-1][1]][i-1][0];
}
}
}
void work(){
int p=0;
for(auto nn:ss){
int l=nn.fi,r=nn.se;
vector<int> sl,sr;
for(l+=M-1,r+=M+1;l^r^1;l>>=1,r>>=1){
if(!(l&1)) sl.push_back(l^1);
if( r&1 ) sr.push_back(r^1);
}
for(auto i:sl){
int hb=hbt(i),bb=M>>hb;
i-=(1<<hb);
int pl=i*bb,tt=ppcnt(pl)&1;
msg("%d %d||\n",pl,pl+bb-1);
cnt[p][30-hb][tt]++;
p=f[p][30-hb][tt];
}
msg("===\n");
reverse(sr.begin(),sr.end());
for(auto i:sr){
int hb=hbt(i),bb=M>>hb;
i-=(1<<hb);
int pl=i*bb,tt=ppcnt(pl)&1;
msg("%d %d||\n",pl,pl+bb-1);
cnt[p][30-hb][tt]++;
p=f[p][30-hb][tt];
}
msg("%d|\n",p);
}
fordown(i,30,1){
forup(j,0,cntn){
cnt[j][i-1][0]+=cnt[j][i][0];
cnt[f[j][i-1][0]][i-1][1]+=cnt[j][i][0];
cnt[j][i-1][1]+=cnt[j][i][1];
cnt[f[j][i-1][1]][i-1][0]+=cnt[j][i][1];
}
}
forup(i,0,cntn){
sum[tr[i][0]]+=cnt[i][0][0];
sum[tr[i][1]]+=cnt[i][0][1];
}
}
void dfs(int x){
for(auto i:e[x]){
dfs(i);
sum[x]+=sum[i];
}
}
}ac;
signed main(){
n=read();q=read();
forup(i,1,n){
int l=read(),r=read();
ss.push_back(mkp(l,r));
}
forup(i,1,q){
scanf(" %s",t+1);
ac.Insert(t,strlen(t+1),i);
}
ac.Build();
ac.work();
ac.dfs(0);
forup(i,1,q){
printf("%lld\n",sum[ed[i]]);
}
}
P5397 [Ynoi2018] 天降之物
题意
有一个长为 $n$ 的序列，维护两个操作（总共进行 $m$ 次，但 lxl 保证 $m=n$）。
1 x y，将序列中所有 $x$ 修改为 $y$2 x y，找出一个位置 $i$ 满足 $a_i=x$，找出一个位置 $j$ 满足 $a_j=y$，使得 $|i-j|$ 最小，并输出 $|i-j|$（下文称这样“最小的 $|i-j|$”为“距离”），如果找不出这样的位置，输出Ikaros。- 强制在线，输入的所有数据在异或上一次答案后在 $[1,10^5]$ 内，所有数不大于 $n$，时限 500ms。
题解
有一个很简单的根号分治做法。
只考虑询问操作，容易想到两种不同的算法：
- 算法一：对于所有 $x$，预处理所有 $y$ 到它的距离 $dis_{x,y}$。对于一个 $x$ 可以 $O(n)$ 扫一遍。时空复杂度均为 $O(Xn)$，其中 $X$ 是不同的 $x$ 个数，查询可以 $O(1)$。
- 算法二：对于所有 $x$，存储它的出现位置集合 $S$，预处理总时空复杂度 $O(n)$。由于具有单调性，查询可以在 $S_x,S_y$ 集合上跑双指针，复杂度 $O(|S_x|+|S_y|)$。
这个看起来就非常根号分治啊。设定一个阈值 $B$，令 $x$ 的出现次数为 $sz_x$，若 $sz_x\ge B \lor sz_y \ge B$ 则使用算法一，此时时空复杂度为 $O(\frac{n^2}{B})$（因为只需要存 $sz_x\ge B$ 的所有 $x$ 与其余数的距离，这样的数最多有 $\frac{n}{B}$ 个），若 $sz_x<B\land sz_y<B$ 则使用算法二，此时单次查询时间复杂度为 $O(B)$，总复杂度 $O(nB)$。当 $B=\sqrt{n}$ 时复杂度即为 $O(n\sqrt{n})$。
考虑如何修改。
首先如果 $sz_x=0$ 或者 $x=y$ 可以直接摆烂，如果 $y=0$ 考虑用打标记的方法修改（比如用 $mp_x$ 存储 $x$ 在序列上实际对应哪个数，这就可以直接 $mp_y\gets mp_x,mp_x\gets 0$）。剩下的就是需要动脑子的了。
由于我们已经用 $mp_x$ 了，所以不妨设 $sz_y>sz_x$（如果不满足直接 swap(mp[x],mp[y]) 即可）。那么只剩下三种情况:
- $sz_x<B,sz_y <B$：这个可以直接遍历 $S_x$ 在序列上改了之后直接把 $S_x,S_y$ 归并到一起。单次操作复杂度显然是根号的。
- $sz_x\ge B,sz_y \ge B$：这个可以考虑 $O(n)$ 遍历整个序列把所有 $x$ 改成 $y$ 然后再计算一遍 $dis_y,z$，由于这样的 $x,y$ 不超过 $\sqrt{n}$ 个（算上初始小于 $B$，后面合成出来的大于等于 $B$ 的显然也不会超过 $\sqrt{n}$）所以这样的合并最多会发生根号次，总复杂度为 $O(n\sqrt{n})$。
- $sz_x<B,sz_y\ge B$：这个不太好直接处理，怎么办呢？一个简单的做法是设置一个缓存区，将 $S_x$ 与 $S_y$ 的缓存区归并。然后查询时将大块与缓存区分开计算。每当缓存区 $\ge B$ 时就合并入 $S_y$。“归并入缓存区”的操作复杂度为根号，“合并入 $S_y$”的操作复杂度为 $O(n)$ 但最多进行 $\sqrt{n}$ 次。总复杂度还是 $O(n\sqrt{n})$。然后你会发现第一种情况可以直接用这种情况来做。
综上，总时空复杂度均为 $O(n\sqrt{n})$。
参考代码
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define forup(i,s,e) for(int i=(s);i<=(e);i++)
#define fordown(i,s,e) for(int i=(s);i>=(e);i--)
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void()
#endif
using namespace std;
#define gc getchar()
inline int read(){
int x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int N=1e5+5,B=500,inf=0x3f3f3f3f;
int n,m,a[N],lans,sz[N],mp[N];
vector<int> tiny[N];
vector<int> dis[N];
set<int> ss;
void build(int x){
dis[x].clear();
dis[x].resize(n+5,inf);
ss.insert(x);
int lst=-1;
forup(i,1,n){
if(a[i]==x){
lst=i;
}else{
if(~lst) dis[x][a[i]]=min(dis[x][a[i]],i-lst);
}
}
lst=-1;
fordown(i,n,1){
if(a[i]==x){
lst=i;
}else{
if(~lst) dis[x][a[i]]=min(dis[x][a[i]],lst-i);
}
}
}
void Merge(vector<int> &a,vector<int> &b){
vector<int> c(a.size()+b.size());
merge(a.begin(),a.end(),b.begin(),b.end(),c.begin());
swap(b,c);
a.clear();
}
signed main(){
n=read();m=read();
forup(i,1,n){
a[i]=read();
++sz[a[i]];
tiny[a[i]].push_back(i);
}
forup(i,1,n){
if(sz[i]){
mp[i]=i;
if(sz[i]>=B){
tiny[i].clear();
build(i);
}
}
}
forup(i,1,m){
int op=read(),x=read(),y=read();
x^=lans;y^=lans;
if(op==1){
if(mp[x]==0||x==y){
continue;
}
if(mp[y]==0){
swap(mp[x],mp[y]);
continue;
}
if(sz[mp[x]]>=B){
swap(mp[x],mp[y]);
}
int u=mp[x],v=mp[y];
for(auto i:ss){
dis[i][v]=min(dis[i][v],dis[i][u]);
dis[i][u]=inf;
}
if(sz[u]>=B){
forup(i,1,n){
if(a[i]==u) a[i]=v;
}
build(v);
tiny[v].clear();
dis[u].clear();
tiny[u].clear();
}else{
for(auto i:tiny[u]){
a[i]=v;
}
Merge(tiny[u],tiny[v]);
dis[u].clear();
tiny[u].clear();
if(tiny[v].size()>=B){
build(v);
tiny[v].clear();
}
}
sz[v]+=sz[u];
sz[u]=0;
mp[x]=0;
ss.erase(u);
}else{
if(mp[x]==0||mp[y]==0){
lans=0;puts("Ikaros");continue;
}
if(x==y){
lans=0;puts("0");continue;
}
int u=mp[x],v=mp[y];
lans=inf;
if(tiny[u].size()&&tiny[v].size()){
int szx=tiny[u].size(),szy=tiny[v].size(),px=0,py=0;
forup(i,1,szx+szy-1){
int tx=tiny[u][px],ty=tiny[v][py];
lans=min(lans,abs(tx-ty));
if(py==szy-1||(px<szx-1&&tx<=ty)){
++px;
}else{
++py;
}
}
}
if(sz[u]>=B) lans=min(lans,dis[u][v]);
if(sz[v]>=B) lans=min(lans,dis[v][u]);
printf("%d\n",lans);
}
}
}
[ABC221G] Jumping sequence
题意
- 在平面直角坐标系上，有一点 $(A,B)$。给你一个长为 $n$ 的序列 $\begin{Bmatrix}d_n\end{Bmatrix}$，表示你每一步的长度。
- 你要决定每一步的方向（上下左右分别为
UDLR），使得最终到达 $(A,B)$，并构造方案。或报告无解。 - $1\le n \le 2000,1\le d_i\le 1800,|A|,|B|\le 3.6\times 10^6$
题解
乍一看显然答案与 $d$ 的顺序是无关的，长得就很像背包。但要把 $d$ 分成四个集合，看起来非常不好做啊。这时候就有一个超级无敌牛逼，让所有人直呼“啊？”的方法：将坐标系顺时针旋转 $45^{\circ}$ 即可。
容易发现这样每个 $d_i$ 都会给 $x,y$ 轴分别贡献 $\pm \frac{d_i}{\sqrt{2}}$，并且两轴是互相独立的。就变成了两个独立的“分成两个集合”的问题。
此时 $(A,B)$ 的横纵坐标分别为 $(\frac{A-B}{\sqrt{2}},\frac{A+B}{\sqrt{2}})$，那么容易发现我们可以把新坐标系的所有信息乘以 $\sqrt{2}$，就是整数了。
为了避免正负号的影响可以假设最初全取负（相当于容量 $+\sum d_i$），然后每把一个改成正的就加 $2d_i$（相当于再将总容量除以 $2$）。这样就变成了一个经典的 $01$ 背包问题。设背包容量为 $C,\max\begin{Bmatrix}d_i\end{Bmatrix}=D$。
一般的 01 背包复杂度是 $O(n\sum d_i)$ 的，考虑如何优化（这道题其实可以直接 bitset，但是有一个更强力的做法）。
这里介绍一个非常强力的算法：$O(nD)$ 判断 01 背包是否能恰好装满。
首先从前往后遍历，直到找到一个 $pos$ 使得 $\sum_{i=1}^{pos-1}d_i\le C,sum_{i=1}^{pos}d_i> C$。接下来就是要在左边扔掉一部分的同时在右边加入一部分。
那么可以想到一个很简单的 DP：设 $f_{l,r,w}$ 表示左端点考虑到 $l$，右端点考虑到 $r$，总体积能否恰好为 $C+w$（$w$ 可能为负数，这个后面解决）。
由于我们想凑出 $C$（即 $w=0$），所以对于 $w>0$ 的状态只考虑从左边扔掉某一个，$w<0$ 的状态只考虑从右边加上某一个，这样 $w$ 的值域就是 $[-D,D]$，可以简单地处理负号问题，有如下转移（此处 $\gets$ 表示取或）：
- $f_{l-1,r,w}\gets f_{l,r,w}$（即往左拓展但不操作）
- $f_{l,r+1,w}\gets f_{l,r,w}$（即往右拓展但不操作）
- $f_{l,r+1,w+d_{r+1}}\gets f_{l,r,w}(w<0)$（即往右拓展并加入对应物品）
- $f_{l-1,r,w-d_{l-1}}\gets f_{l,r,w}(w>0)$（即往左拓展并扔掉对应物品）
这样复杂度变成 $O(n^2D)$ 了，但是优化的空间变大了。容易想到 DP 值只存存在性过于浪费了，考虑设 $g_{r,w}$ 表示若 $f_{l,r,w}=1$，$l$ 最大是多少，若不存在则取 $0$。
这样的转移也很简单（此处 $\gets$ 表示取 $\max$）：
- $g_{r+1,w}\gets f_{l,r,w}$
- $g_{r+1,w+d_{r+1}}\gets f_{l,r,w}$
- $g_{r+1,w-d_{l}}\gets l(w>0,l\in[1,g_{r,w}-1])$
这里不需要考虑向左拓展且不操作，因为 $g_{r,w}$ 存的是最大值，若向左拓展且不操作显然不优。
但是容易发现单次转移的复杂度变成 $O(n)$ 了，复杂度仍是 $O(n^2D)$，考虑寻找单调性。容易发现若 $g_{r+1,w-d_l}<g_{r-1,w}$，那么会从 $g_{r-1,w}\to g_{r,w-d_l}\to g_{r+1,w-d_l}$ 的路径转移一次。所以第三个转移时只需要考虑 $l\in [g_{r-1,w},g_{r,w}-1]$ 即可。由于对于同一个 $w$，$g_{r,w}$ 是随着 $r$ 单调不减的（显然，因为每次转移必定会和 $g_{r-1,w}$ 取 $\max$），故总复杂度为 $O(D\sum (g_{r,w}-g{r-1,w}))=O(nD)$，然后就能做了。
总复杂度 $O(nD)$，注意输出方案自己推一下。
参考代码
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define forup(i,s,e) for(int i=(s);i<=(e);i++)
#define fordown(i,s,e) for(int i=(s);i>=(e);i--)
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void()
#endif
using namespace std;
using pii=pair<int,int>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
inline int read(){
int x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int N=2005,inf=0x3f3f3f3f;
int n,A,B,d[N],D;
int seq[2][N];
int dp[N][N<<1];
pii pre[N][N<<1];
void getseq(int i,int j,int p){
msg("%d %d||\n",i,j);
if(pre[i][j].fi==-1){
return;
}else if(pre[i][j].fi==0){
getseq(i-1,j,p);
}else if(pre[i][j].fi==1){
seq[p][pre[i][j].se]=1;
getseq(i-1,j-d[pre[i][j].se],p);
}else if(pre[i][j].fi==2){
seq[p][pre[i][j].se]=0;
getseq(i,j+d[pre[i][j].se],p);
}
}
void work(int C,int p){
int sum=0,r=1;
while(r<=n&&sum+d[r]<=C){
sum+=d[r];
++r;
}
if(r==n+1&&sum!=C){
msg("1");puts("No");
exit(0);
}
forup(i,1,r-1){
seq[p][i]=1;
}
if(sum==C){
return;
}
forup(i,1,n){
forup(j,1,2*D){
dp[i][j]=0;pre[i][j]=mkp(0,0);
}
}
dp[r-1][D+sum-C]=r;
pre[r-1][D+sum-C]=mkp(-1,-1);
forup(i,r,n){
forup(j,1,2*D){
if(dp[i][j]<dp[i-1][j]){
dp[i][j]=dp[i-1][j];
pre[i][j]=mkp(0,0);
}
}
forup(j,1,D){
if(dp[i][j+d[i]]<dp[i-1][j]){
dp[i][j+d[i]]=dp[i-1][j];
pre[i][j+d[i]]=mkp(1,i);
}
}
fordown(j,2*D,D+1){
forup(k,dp[i-1][j],dp[i][j]-1){
if(dp[i][j-d[k]]<k){
dp[i][j-d[k]]=k;
pre[i][j-d[k]]=mkp(2,k);
}
}
}
}
if(dp[n][D]==0){
msg("2");puts("No");
exit(0);
}
getseq(n,D,p);
}
signed main(){
n=read();
int a=read(),b=read();
A=a-b;B=a+b;
forup(i,1,n){
d[i]=read();
A+=d[i];B+=d[i];
D=max(D,d[i]);
}
if(A<0||B<0||(A&1)||(B&1)){
puts("No");
return 0;
}
A>>=1;B>>=1;
msg("A %d==\n",A);
work(A,0);
msg("B %d==\n",B);
work(B,1);
forup(i,0,1){
forup(j,1,n){
msg("%d ",seq[i][j]);
}
msg("|\n");
}
puts("Yes");
forup(i,1,n){
if( seq[0][i]&& seq[1][i]) putchar('R');
if(!seq[0][i]&& seq[1][i]) putchar('U');
if(!seq[0][i]&&!seq[1][i]) putchar('L');
if( seq[0][i]&&!seq[1][i]) putchar('D');
}
}
P6326 Shopping
题意
- 给定一棵 $n$ 个点的树，每个点上有若干物品，其中每个点有三个权值 $w_i,c_i,d_i$，分别代表对应结点上物品权值、价格、数量。
- 现在你需要选定一个连通块，其中每个物品至少买一个。在总价格不超过 $m$ 的情况下最大化权值和。
- $1\le n\le 500,1\le c_i\le m,\le 4000,1\le w_i \le 4000,1\le d_i \le 100$，多测。
题解
多重背包部分没什么说的，二进制优化，比较老生常谈。重点来说一下这种树上问题怎么做。
考虑钦定选一个点 $x$（就是说直接点分治解决，下文叙述单个连通块内如何解决）。那么就是一个根必选的有根树，显然如果不选某个点那么它的子树必定都不能选，那可以考虑用 dfs 序直接跳过其子树。然后大体思路就这样，令 $dp_{i,j}$ 表示考虑到 dfs 序上 $[1,n]$，消耗代价 $j$ 最多能得到多少权值，具体转移如下：
- $dp_{i,j}=dp_{i+1,j-c_{I}}+w_{I}$
- 对 $dp_i$ 跑多重背包，转移不好概括，但是这里的 $d$ 记得 $-1$。
- $dp_{i,j}=\max(dp_{i,j},dp_{next_i,j})$
其中 $I$ 表示 dfs 序 $i$ 对应的点，$next_i$ 表示跳过 $i$ 子树后的下一个点。
然后 $dp_{1,m}$ 即答案。
复杂度 $O(\sum_i nm\log n\log d_i)$，还是比较轻松的。
总结下来就是若 DP 信息与连通块中具体的点有关可以考虑在 dfs 序上倒着 DP。
参考代码
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define forup(i,s,e) for(int i=(s);i<=(e);i++)
#define fordown(i,s,e) for(int i=(s);i>=(e);i--)
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void()
#endif
using namespace std;
using pii=pair<int,int>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
inline int read(){
int x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int N=505,inf=0x3f3f3f3f;
int t,n,m,w[N],c[N],d[N],ans;
vector<pii> itm[N];
int dp[N][4005];
struct edge{
int v,nxt;
}e[N<<1];
int head[N],cnte;
void adde(int u,int v){
e[++cnte]=edge{v,head[u]};head[u]=cnte;
e[++cnte]=edge{u,head[v]};head[v]=cnte;
}
int vis[N];
int sz[N],mx[N],rt,als;
void dfs1(int x,int fa){
sz[x]=1;mx[x]=0;
for(int i=head[x];i;i=e[i].nxt){
int v=e[i].v;
if(vis[v]||v==fa) continue;
dfs1(v,x);
sz[x]+=sz[v];
mx[x]=max(mx[x],sz[v]);
}
mx[x]=max(mx[x],als-sz[x]);
if(rt==-1||mx[x]<mx[rt]) rt=x;
}
int st[N],ed[N],mp[N],Tm;
void dfs2(int x,int fa){
st[x]=++Tm;mp[Tm]=x;
for(int i=head[x];i;i=e[i].nxt){
int v=e[i].v;
if(vis[v]||v==fa) continue;
dfs2(v,x);
}
ed[x]=Tm;
}
void dfz(int x,int ps){
vis[x]=1;
Tm=0;dfs2(x,0);
fordown(i,Tm,1){
forup(j,c[mp[i]],m){
dp[i][j]=dp[i+1][j-c[mp[i]]]+w[mp[i]];
}
for(auto ii:itm[mp[i]]){
int c=ii.fi,w=ii.se;
fordown(j,m,c){
dp[i][j]=max(dp[i][j],dp[i][j-c]+w);
}
}
forup(j,0,m){
dp[i][j]=max(dp[i][j],dp[ed[mp[i]]+1][j]);
}
}
ans=max(ans,dp[1][m]);
forup(i,1,Tm){
forup(j,0,m){
dp[i][j]=0;
}
}
for(int i=head[x];i;i=e[i].nxt){
int v=e[i].v;
if(vis[v]) continue;
rt=-1;als=(sz[v]<sz[x]?sz[v]:ps-sz[x]);
dfs1(v,x);
dfz(rt,als);
}
}
void solve(){
n=read();m=read();
forup(i,1,n) w[i]=read();
forup(i,1,n) c[i]=read();
forup(i,1,n) d[i]=read()-1;
cnte=0;mem(head,0);mem(vis,0);ans=0;
forup(i,1,n){
itm[i].clear();
int t=1;
while(t<d[i]){
itm[i].push_back(mkp(c[i]*t,w[i]*t));
d[i]-=t;
t<<=1;
}
if(d[i]) itm[i].push_back(mkp(c[i]*d[i],w[i]*d[i]));
}
forup(i,1,n-1){
int u=read(),v=read();
adde(u,v);
}
rt=-1;als=n;
dfs1(1,0);
dfz(rt,als);
printf("%d\n",ans);
}
signed main(){
t=read();
while(t--){
solve();
}
}
P10197 [USACO24FEB] Minimum Sum of Maximums P
题意
- 有一个长度为 $n$ 的序列 $\begin{Bmatrix}a_n\end{Bmatrix}$，定义序列的权值为 $\sum_{i=1}^{n-1}\max(a_i,a_{i+1})$。
- 现在规定 $k$ 个位置不能动，其余位置随意交换，问得到的序列权值最小为多少。
- $2\le n\le 300,0\le k\le \min(n,6),1\le a_i\le 10^6$
题解
考虑最大值之和不好做。但是注意到 $\max(a,b)=\frac{a+b+|a-b|}{2}$，容易发现 $a+b$ 这一部分是固定的（对于边界情况，解决办法是在 $a_0,a_{n+1}$ 分别塞一个大于 $\max\begin{Bmatrix}a_i\end{Bmatrix}$ 的数，最后减掉），那么只需要考虑最小化 $\sum_{i=1}^{n-1} |a_i-a_{i+1}|$ 即可。
先不考虑 $k$ 个位置不能动，显然排成单调不减/单调不增是最小的，此时贡献为 $\max\begin{Bmatrix}a_i\end{Bmatrix}-\min\begin{Bmatrix}a_i\end{Bmatrix}$（并且容易发现任何序列无论怎么排都会产生至少这么多贡献，一个简单方法是考虑把从最小值到最大值的单调子序列取出来），下文令 $mn=\min\begin{Bmatrix}a_i\end{Bmatrix},mx=\max\begin{Bmatrix}a_i\end{Bmatrix}$。
然后考虑只有左右两个固定的（设它们两个分别为 $a_L,a_R$）。容易发现无论怎么排，必定都会产生 $|a_L-mn|+|a_R-mx|+mx-mn$ 的贡献（或者 $a_L,a_r$ 反过来）。那么显然把 $mn$ 分给较小的那个是较优的，即确定一个区间内数的集合 $P$ 中的最大最小值后，最小贡献是唯一确定的，此处（以及下文）的“区间”均指两个固定的数中间夹的空格。
下面考虑每一个区间塞哪些数。给出引理：存在最优解满足不存在两区间 $I,J$，使得 $mn_I<mn_J<mx_I<mx_J$（即两区间内的数不是包含就是相离）。
证明考虑调整，若出现上面的连不等式，显然可以通过交换 $I,J$ 内一定数得到 $mn_I<mx_I'<mn_J'<mx_J$（满足上述情况时 $|I|$ 和 $|J|$ 必不可能等于 $1$，不存在需要动 $mn_I$ 和 $mx_J$ 的情况），此时 $mx_I'<mx_I$ ，容易发现贡献中与 $mx_I$ 相关的是 $mx_I+|a_R-mx_I|$，分类讨论拆绝对值容易发现这个数不是不变就是变小，对于 $mn_J'$ 也同理。
那么把自由的数拿出来，容易想到在它们按单调不降排成的序列 $\begin{Bmatrix}b_i\end{Bmatrix}$ 上区间 DP。具体来说，令 $f_{l,r,S}$ 表示考虑 $[b_l,b_r]$，已经把 $S$ 集合内的区间填满（$S$ 是一个元素为“区间”的集合，这里比较容易混淆），所能得到的最小贡献。因为两区间内的数不是包含就是相离，所以每次只考虑一个区间的 $b_i$ 是能概括所有情况的。
转移考虑这个位置作不作最小值/最大值，以及两相离区间的合并：
- $f_{l,r,S}\gets \min(f_{l+1,r,S},f_{l,r-1,S})$，表示 $l,r$ 都不作区间边界，预留给后面的区间。
- $f_{l,r,S}\gets \min_{x\in S}\begin{Bmatrix}f_{l+1,r-1,S-\begin{Bmatrix}x\end{Bmatrix}}+w(b_l,b_r,x)\end{Bmatrix}$，其中 $w(l,r,x)$ 表示 $x$ 区间最大最小值分别为 $l,r$ 时所能产生的贡献。这个表示 $l,r$ 分别作最大最小值新开一个区间的贡献。这个转移可以只在 $r-l+1=sz_S$ 时做，$sz_S$ 表示 $S$ 集合内区间总长度，因为当 $sz_S$ 恰好等于 $r-l+1$ 时所得到的的答案必定是不劣的，证明参考上文的调整法。
- $f_{l,r,S}\gets \min_{S'\subsetneq S}\begin{Bmatrix}f_{l,l+sz_{S'}-1,S'}+f_{l+sz_{S'},r,S-S'}\end{Bmatrix}$，即合并两相离区间，这里仍能只在 $r-l+1=sz_S$ 时做，证明类似。
对于复杂度，第一个转移单次的复杂度是 $O(1)$，总共为 $O(n^2 2^n)$。第二个只做 $O(2^kn)$ 次，总共为 $O(kn2^k)$，第三个也只做 $O(n2^k)$ 次，因为要子集枚举所以复杂度是 $O(n2^k3^k)$ 次。
瓶颈在转移三，总复杂度为 $O(n6^k)$。
参考代码
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define forup(i,s,e) for(int i=(s);i<=(e);i++)
#define fordown(i,s,e) for(int i=(s);i>=(e);i--)
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void()
#endif
using namespace std;
#define gc getchar()
inline int read(){
int x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int N=305,inf=0x3f3f3f3f;
int n,k,a[N],b[N],ans,sz[1<<8];
vector<int> seq;
int l[10],r[10],cntr;
int dp[N][N][1<<8];
int calc(int rg,int al,int ar){
int pl=a[l[rg]],pr=a[r[rg]];
if(pl>pr) swap(pl,pr);
return abs(pl-al)+abs(pr-ar)+ar-al;
}
signed main(){
n=read();k=read();
forup(i,1,n){
a[i]=read();
ans+=a[i]*2;
}
a[0]=a[n+1]=1e7;
ans+=2e7;
forup(i,1,k){
int x=read();
b[x]=1;
}
int lst=0;
forup(i,1,n){
if(b[i]){
if(lst<i-1){
++cntr;
l[cntr]=lst;r[cntr]=i;
sz[1<<(cntr-1)]=r[cntr]-l[cntr]-1;
}else{
ans+=abs(a[i]-a[i-1]);
}
lst=i;
}else{
seq.push_back(a[i]);
}
}
if(lst<n){
++cntr;
l[cntr]=lst;r[cntr]=n+1;
sz[1<<(cntr-1)]=r[cntr]-l[cntr]-1;
}else{
ans+=abs(a[n+1]-a[n]);
}
forup(i,1,(1<<cntr)-1){
if(i==(i&-i)) continue;
int j=i;
while(j){
sz[i]+=sz[j&-j];
j-=j&-j;
}
}
sort(seq.begin(),seq.end());
int siz=seq.size();
mem(dp,0x3f);
forup(i,1,siz+1){
dp[i][i-1][0]=dp[i+1][i-1][0]=0;
}
forup(len,1,siz){
forup(l,1,siz-len+1){
int r=l+len-1;
forup(S,0,(1<<cntr)-1){
if(sz[S]>r-l+1) continue;
dp[l][r][S]=min(dp[l+1][r][S],dp[l][r-1][S]);
if(sz[S]==r-l+1){
forup(i,1,cntr){
if(!S&(1<<(i-1))) continue;
dp[l][r][S]=min(dp[l][r][S],dp[l+1][r-1][S^(1<<(i-1))]+calc(i,seq[l-1],seq[r-1]));
}
for(int i=(S-1)&S;i;i=(i-1)&S){
dp[l][r][S]=min(dp[l][r][S],dp[l+sz[i]][r][S^i]+dp[l][l+sz[i]-1][i]);
}
}
}
}
}
ans+=dp[1][siz][(1<<cntr)-1];
ans/=2;
ans-=2e7;
printf("%d\n",ans);
}
乐，正好 $99$ 行。
CF1830D Mex Tree
题意
- 给定一棵 $n$ 个结点的树，点有点权，点权为 $0$ 或 $1$。你需要给一种指定点权的方案，使得每一条路径的点权 $\mathrm{mex}$ 之和最大。
- $1\le \sum n\le 2\times 10^5$，多组数据。
题解
容易发现 $\mathrm{mex}$ 只有 $0,1,2$ 三种，那么第一反应肯定是最大化 $2$ 的个数。显然一眼就能看出按二分图染色能得到一个看起来很优的答案，因为除去长度为 $1$ 的链（其实就是点）外其它链的 $\mathrm{mex}$ 均为 $2$。但是学 OI 学的比较久的就能感受到一股“显然不是最优解”的感觉。反例也比较好构造，就搞个菊花图然后把中间的点拆成两个连起来，这样中间两个取 $1$ 其余取 $0$ 比较优。
但是容易发现这说明不管什么图答案必定大于等于 $n(n-1)+\left\lceil\frac{n}{2}\right\rceil$，即最多有 $O(n)$ 条链没有产生 $2$ 的贡献。
容易发现一条链没产生贡献当且仅当这条链上只有一种颜色，换句话说，同一种颜色的连通块大小不会超过 $O(\sqrt{n})$ 级别。
假设所有路径的权值均为 $2$，那么答案就是 $n(n+1)$。考虑减去多算的，那么显然要最小化减去的东西。容易想到一个子树 DP，令 $f_{u,i,0/1}$ 表示只考虑点 $u$ 及其子树，$u$ 所在连通块大小为 $i$，颜色为 $0/1$，整个子树的最小贡献。
转移比较简单，就是考虑当前点和下一个子树颜色是否一样，然后合并即可，注意上下界，不要写假了。具体转移就不列了。
因为 $O(n\sqrt{n})$ 的空间存不下，所以需要用动态数组。
下面证明时间复杂度（其实很经典，证明 $n$ 个点，体积为 $k$，每个点至少占 $1$ 体积的树上背包复杂度是 $O(nk)$）：
把所有子树按是否比 $k$ 大分为“小的”和“大的”。
首先考虑小子树合到大子树上。小子树合到大子树后就始终属于大子树了，所以每个点只会出现一次这种情况，故复杂度为 $O(nk)$。
然后考虑小子树合到小子树上，这种情况始终抵不到上界。那么假如 $v$ 合到 $u$ 上，可以看做是 $u,v$ 子树中分别选一个点做匹配。由于任意两个点只会在 $\mathrm{lca}$ 处相遇一次，故大小为 $x$ 的小子树中合并的总复杂度是 $O(x^2)$ 的。那么考虑所有极大的小子树，显然每一棵大小都为 $k$ 时复杂度最劣，为 $O(\frac{n}{k}\times k^2)=O(nk)$。
最后考虑两大子树合并。容易发现互不包含的大子树最多有 $\frac{n}{k}$ 个，那么最多合 $O(\frac{n}{k})$ 次，复杂度 $O(\frac{n}{k}\times k^2)=O(nk)$。
综上，这道题复杂度是 $O(n\sqrt{n})$。
参考代码
#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define forup(i,s,e) for(int i=(s);i<=(e);i++)
#define fordown(i,s,e) for(int i=(s);i>=(e);i--)
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void()
#endif
using namespace std;
using i64=long long;
using pii=pair<int,int>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
inline int read(){
int x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int N=2e5+5,B=500,inf=0x3f3f3f3f;
int t,n,p;
i64 ans;
vector<int> e[N];
int sz[N];
vector<pii> dp[N];
void dfs(int x,int fa){
sz[x]=1;
dp[x].resize(2);
dp[x][1]=mkp(1,2);
for(auto v:e[x]){
if(v==fa) continue;
dfs(v,x);
if(sz[x]<=p) dp[x].resize(min(sz[x]+sz[v],p)+1,mkp(inf,inf));
int m1=inf,m2=inf;
forup(i,1,dp[v].size()-1){
m1=min(m1,dp[v].at(i).fi);
m2=min(m2,dp[v].at(i).se);
}
fordown(i,dp[x].size()-1,1){
if(i<=sz[x]){
dp[x].at(i).fi+=m2;
dp[x].at(i).se+=m1;
}
forup(j,max(1,i-sz[x]),min(i-1,(int)dp[v].size()-1)){
dp[x].at(i).fi=min(dp[x].at(i).fi,dp[x].at(i-j).fi+dp[v].at(j).fi+j*(i-j));
dp[x].at(i).se=min(dp[x].at(i).se,dp[x].at(i-j).se+dp[v].at(j).se+j*(i-j)*2);
}
}
dp[v].clear();dp[v].shrink_to_fit();
sz[x]+=sz[v];
}
e[x].clear();
}
void solve(){
n=read();
ans=1ll*n*(n+1);
forup(i,1,n-1){
int u=read(),v=read();
e[u].push_back(v);
e[v].push_back(u);
}
p=int(sqrt(n))+5;
dfs(1,0);
int mn=inf;
forup(i,1,dp[1].size()-1){
mn=min({mn,dp[1].at(i).fi,dp[1].at(i).se});
}
dp[1].clear();dp[1].shrink_to_fit();
ans-=mn;
printf("%lld\n",ans);
}
signed main(){
t=read();
while(t--){
solve();
}
}
CF755F PolandBall and Gifts
题意
- 给定一个长度为 $n$ 的排列 $p_i$，你要从中选择 $m$ 个涂黑。
- 令权值为 $\sum_{i=1}^n[c_i=1\lor c_{p_i} =1]$，其中 $c_i=1$ 表示 $i$ 为黑色。
- 问权值可能的最大值/最小值分别是多少。
- $2\le n \le 10^6,0\le m \le n$
题解
远古水紫。
看到排列考虑置换环。
先求最大值。容易发现在置换环上各一个涂一个产生的权值最大（这样每涂一个能产生 $2$ 的权值），但奇数环最后一次只会产生一个权值，解决办法是贪心的先选能产生 $2$ 贡献的，再考虑产生 $1$ 贡献的。这部分比较简单。
然后考虑最小值。容易想到理想情况是把所有黑色涂成连续的，这样除去其中一个端点以外其它每个点都只产生一个贡献。又容易发现如果恰好填满一个环那么所有点都只产生一个贡献。所以我们就希望恰好能涂满若干个环，那么容易想到 01 背包。
但是直接 01 背包是 $O(nm)$ 的，显然会 TLE。怎么办呢？这里考虑一个经典结论：总和为 $n$ 的若干个数中，最多有 $O(\sqrt{n})$ 种不同的数。证明也非常简单，考虑最大化数的种类数显然应该类似 $1+2+3\dots k$ 地构造，那么此时总和为 $\frac{k^2+k}{2}$，是 $k^2$ 级别的。那显然 $k$ 是 $O(\sqrt{n})$ 级别的。
那么多重背包加二进制优化即可，复杂度 $O(\frac{m\sqrt{n}\log n}{w})$。
参考代码
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define forup(i,s,e) for(int i=(s);i<=(e);i++)
#define fordown(i,s,e) for(int i=(s);i>=(e);i--)
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void()
#endif
using namespace std;
#define gc getchar()
inline int read(){
int x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int N=1e6+5,inf=0x3f3f3f3f;
int n,m,p[N],vis[N],cnt[N],ans1,ans2;
int dfs(int x){
if(vis[x]) return 0;
vis[x]=1;
return dfs(p[x])+1;
}
bitset<N> dp;
signed main(){
n=read();m=read();
forup(i,1,n){
p[i]=read();
}
forup(i,1,n){
if(!vis[i]){
++cnt[dfs(i)];
}
}
int m1=m,cnto=0;
forup(i,1,n){
int t=min(cnt[i]*(i>>1),m1);
m1-=t;
ans1+=t*2;
if(i&1&&cnt[i]) cnto+=cnt[i];
if(!m1) break;
}
if(m1){
int t=min(cnto,m1);
ans1+=t;
}
dp.flip(0);
forup(i,1,n){
if(cnt[i]){
int d=1,p=cnt[i];
while(p>=d){
dp=dp|(dp<<d*i);
p-=d;d<<=1;
}
dp=dp|(dp<<p*i);
}
}
if(dp[m]) ans2=m;
else ans2=m+1;
printf("%d %d",ans2,ans1);
}
但是其实还可以把那个 $\log$ 去掉，要用一个叫 3k-trick 的东西。
具体来说，容易发现二进制拆分后仍然有很多相同的数，那么其实可以考虑从小到大遍历，每有三个相同的 $k$ 就把其中两个合起来变成 $2k$，容易发现对结果不产生影响，能拼出来的数照样能拼出来，然后由于不同的数最多有 $O(\sqrt{n})$ 种，每种最多俩，那么相当于只有 $\sqrt{n}$ 个物品的 01 背包。总复杂度 $O(\frac{m\sqrt{n}}{w})$。
参考代码片段
P2305 [NOI2014] 购票
题意
- 给定一棵 $n$ 个点边带权的树，每个店有三个权值 $p_i,q_i,l_i$，代表跳到距离为 $x$ 的祖先需要消耗 $p_i\cdot x +q_i$ 的代价，最多跳到距离为 $l_i$ 的祖先。
- 问每个点跳到根节点的最小代价。
- 每个点到根的距离不超过 $2\times 10^{11}$，$0\le p_i\le 10^6,0\le q_i\le 10^{12}$，其余数据在合理范围内，保证 $l_i$ 大于 $i$ 到其父亲的距离。
题解
一眼就能看出来从根到每个点是更好做的。有一个非常显然的 DP，转移如下：
$$dp_u\gets \min_{v\in\mathrm{ancestor_{\mathit{u}}}}^{dis_u-dis_v\le l_u}\begin{Bmatrix}dp_v +(dis_u-dis_v)p_u+q_u\end{Bmatrix}$$
其中 $dis_u$ 表示 $u$ 和根结点的距离，$\mathrm{ancestor_{\mathit{u}}}$ 是 $u$ 的祖先集合。
这个东西一看就非常斜率优化，然后就是比较版的对 $dis$ 离散化后用线段树维护凸包单点修区间查，这部分略过。注意如果用向量维护叉乘会爆 long long，记得开 __int128。
但是容易发现和序列一直往后加相比，一棵树的遍历过程类似于栈，对于末尾有“加入”和“弹出”两个操作，这个怎么用凸包维护呢？
这种时候不要被 STL 局限了想象力，考虑手写栈是怎么做的。容易发现“弹出”的部分还在那个地方没动过，只是之后的操作可能把它们覆盖了。观察斜优的过程容易发现每个点的操作必定是弹出若干个后，再压入一个，那么在内存上就只有一个地方被修改了。可以把修改前栈的大小以及内存上被修改的那个值存下来，回滚时改回去即可。
复杂度瓶颈在于线段树套凸包的区间查需要在每个结点上二分，复杂度 $O(n\log^2 n)$。
参考代码
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define forup(i,s,e) for(int i=(s);i<=(e);i++)
#define fordown(i,s,e) for(int i=(s);i>=(e);i--)
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void()
#endif
using namespace std;
#define fi first
#define se second
#define mkp make_pair
using i64=long long;
using i128=__int128;
#define gc getchar()
inline i64 read(){
i64 x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int N=2e5+5;
const i64 inf=8e18;
void print(i128 x,bool flag=true){
#ifdef DEBUG
if(!x){
if(flag) putchar('0');
return;
}
if(x<0){
x=-x;
putchar('-');
}
print(x/10,false);
putchar(x%10+'0');
#endif
}
i64 n,t,f[N],d[N],p[N],q[N],l[N];
vector<int> e[N];
struct Point{
i64 x,y;
Point operator -(const Point &r){
return Point{x-r.x,y-r.y};
}
};
i64 dp[N],dis[N];
i128 cross(Point a,Point b){
return (i128)a.x*b.y-(i128)a.y*b.x;
}
vector<i64> lsh;
int find(i64 x){
return lower_bound(lsh.begin(),lsh.end(),x)-lsh.begin()+1;
}
struct SegTree{
#define mid ((l+r)>>1)
#define lson l,mid,id<<1
#define rson mid+1,r,id<<1|1
vector<Point> conv[N<<2];
vector<pair<Point,int> > sv[N<<2];
int top[N<<2];
void Build(int l=1,int r=n,int id=1){
conv[id].resize(r-l+1);top[id]=0;
if(l==r) return;
Build(lson);Build(rson);
}
void Modify(int P,Point X,int l=1,int r=n,int id=1){
pair<Point,int> tt=mkp(Point{0,0},0);
tt.se=top[id];
while(top[id]>1&&cross(conv[id][top[id]-1]-conv[id][top[id]-2],X-conv[id][top[id]-1])<=0) --top[id];
tt.fi=conv[id][top[id]];
sv[id].push_back(tt);
conv[id][top[id]++]=X;
if(l==r) return;
if(P<=mid) Modify(P,X,lson);
else Modify(P,X,rson);
}
void Rollback(int P,int l=1,int r=n,int id=1){
conv[id][--top[id]]=sv[id].back().fi;
top[id]=sv[id].back().se;
sv[id].pop_back();
if(l==r) return;
if(P<=mid) Rollback(P,lson);
else Rollback(P,rson);
}
i64 Query(int L,int R,int X,int l=1,int r=n,int id=1){
if(L<=l&&r<=R){
if(top[id]==0) return inf;
i64 ll=0,rr=top[id]-2,mm;
while(ll<rr){
mm=(ll+rr)>>1;
if(cross(conv[id][mm+1]-conv[id][mm],Point{1,p[X]})>0) ll=mm+1;
else rr=mm;
}
if(ll==top[id]-2&&cross(conv[id][ll+1]-conv[id][ll],Point{1,p[X]})>0) ++ll;
return conv[id][ll].y-p[X]*conv[id][ll].x+dis[X]*p[X]+q[X];
}
i64 ans=inf;
if(L<=mid) ans=min(ans,Query(L,R,X,lson));
if(mid< R) ans=min(ans,Query(L,R,X,rson));
return ans;
}
}mt;
void dfs1(int x){
dis[x]=dis[f[x]]+d[x];
for(auto i:e[x]){
dfs1(i);
}
}
void dfs(int x){
int dd=find(dis[x]);
if(x!=1){
dp[x]=mt.Query(find(dis[x]-l[x]),dd-1,x);
}
mt.Modify(dd,Point{dis[x],dp[x]});
for(auto i:e[x]){
dfs(i);
}
mt.Rollback(dd);
}
signed main(){
n=read();t=read();
forup(i,2,n){
f[i]=read();
e[f[i]].push_back(i);
d[i]=read();p[i]=read();q[i]=read();l[i]=read();
}
dp[1]=0;
dfs1(1);
forup(i,1,n) lsh.push_back(dis[i]);
sort(lsh.begin(),lsh.end());
lsh.erase(unique(lsh.begin(),lsh.end()),lsh.end());
mt.Build();
dfs(1);
forup(i,2,n){
printf("%lld\n",dp[i]);
}
}