shadowice1984的练习赛 赛后题解
shadowice1984
2018-12-13 21:26:42
感觉这是一场非常休闲的场次啊，可能是你站历史上最水的一场rated赛了
由于是一整场比赛的题解，所以细节方面不会写太多，请各位聚聚自行发题解来补充官方题解的细节吧~
~~顺便说一句不卡常可能是假的，当我想卡常的时候我会出几个小测试点然后把平均运行时间拉下去，这样就符合平均运行时间的二倍要求了~~
## A:
$\text{shadowice1984}$被noip的d2t2虐惨了，因此他出了一道打表找规律题~~(雾)~~作为本场比赛的T1
通过观察我们可以得到这个式子~~(smg啊)~~
$$a(n) \equiv 233230706×(94153035^{n}-905847205^{n}) \mod (10^9+7)$$
然后我们发现我们需要资瓷$O(1)$的快速幂，这该如何解决呢？
我们发现事实上我们只需要回答两个数字的$n$次幂是多少，并且由于费马小定理的存在，指数是$10^9$级别的
那么我们可以将$a^{n}$表示成$a^{65536k+r}$的形式,显然k和r的取值都不超过65536，因此我们打4个长度为65536的表即可$O(1)$回答每个询问了啦~
好了问题来了刚才的式子显然不是打表找规律得来的……
事实上我们是手玩出了$a(n)$的通项公式，这个东西可以待定系数法/特征方程/生成函数/人类智慧得出，这里给一种生成函数的推倒方法
设这个数列的生成函数为$G(z)$
$$G(z)=233zG(z)+666z^{2}G(z)+z$$
$$(1-233z-666z^2)G(z)=z$$
$$G(z)=\frac{z}{1-233z-666z^2}$$
设$x_{1},x_{2}$为方程$1-233x-666x^2=0$的两个根
$$G(z)=\frac{z}{-666(x_{1}-z)(x_{2}-z)}$$
$$G(z)=\frac{z}{-666}×\frac{1}{(x_{1}-z)(x_{2}-z)}$$
$$G(z)=\frac{z}{-666(x_{1}-x_{2})}×\frac{x_{1}-z+z-x_{2}}{(x_{1}-z)(x_{2}-z)}$$
$$G(z)=\frac{z}{-666(x_{1}-x_{2})}×(\frac{1}{x_{2}-z}-\frac{1}{x_{1}-z})$$
$$G(z)=\frac{1}{-666(x_{1}-x_{2})}×(\frac{1}{x_{2}}×\frac{z}{1-\frac{z}{x_{2}}}-\frac{1}{x_{1}}×\frac{z}{1-\frac{z}{x_{1}}})$$
根据$\frac{z}{1-\lambda z}$是数列$0,1,\lambda^{1},\lambda^{2},\lambda^{3}$的生成函数可知
$$a(n)=\frac{1}{-666(x_{1}-x_{2})}×((\frac{1}{x_{2}})^{n}-(\frac{1}{x_{1}})^{n})$$
将$$x_{1,2}=\frac{233\pm \sqrt{56953}}{-1332}$$代入得
$$a(n)=\frac{1}{\sqrt{56953}}((\frac{233+\sqrt{56953}}{2})^{n}-(\frac{233-\sqrt{56953}}{2})^{n})$$
我们通过暴力发现$56953$在$1e9+7$下有二次剩余(因为出题人给你凑好了模数)，所以代入一下就得到了一开始的式子辣~
复杂度$O(T)$
当然由上面的式子我们发现循环节只有$10^9$因此分块矩乘可以过这题(其实会比较慢但是懒得卡了)
上代码~
```C
// luogu-judger-enable-o2
#include<cstdio>
#include<algorithm>
using namespace std;typedef long long ll;const ll mod=1e9+7;const ll sqr=188305837;
namespace Mker
{
unsigned long long SA,SB,SC;
void init(){scanf("%llu%llu%llu",&SA,&SB,&SC);}
unsigned long long rand()
{
SA^=SA<<32,SA^=SA>>13,SA^=SA<<1;
unsigned long long t=SA;
SA=SB,SB=SC,SC^=t^SA;return SC;
}
}
const ll x1=94153035;const ll x2=905847205;const ll K=233230706;
const ll x3=64353223;const ll x4=847809841;
ll mi1[65536+10];ll mi2[65536+10];ll mi3[65536+10];ll mi4[65536+10];
inline ll po(ll a,ll p){ll r=1;for(;p;p>>=1,a=a*a%mod)if(p&1)r=r*a%mod;return r;}
# define pw1(x) (mi3[x>>16]*mi1[x&65535]%mod)
# define pw2(x) (mi4[x>>16]*mi2[x&65535]%mod)
int T;int ans;
int main()
{
//freopen("tst10.in","r",stdin);freopen("tst10.out","w",stdout);
mi1[0]=1;for(int i=1;i<65536;i++)mi1[i]=mi1[i-1]*x1%mod;
mi2[0]=1;for(int i=1;i<65536;i++)mi2[i]=mi2[i-1]*x2%mod;
mi3[0]=1;for(int i=1;i<65536;i++)mi3[i]=mi3[i-1]*x3%mod;
mi4[0]=1;for(int i=1;i<65536;i++)mi4[i]=mi4[i-1]*x4%mod;
scanf("%d",&T);Mker::init();unsigned long long n;
for(int i=1;i<=T;i++)n=Mker::rand(),n%=(mod-1),ans^=K*(pw1(n)+mod-pw2(n))%mod;
printf("%d",ans);return 0;
}
```
## B:
STO $\text{zhoutb2333}$ Orz
~~可能左闭右开的线段树会坑了一批人~~
~~体谅一下出题人啊，他不会写全是闭区间的线段树~~
线段树上的问题就用线段树来搞定，线段树上每个节点维护4个值
$$(pre,suf,ans,iso)$$
分别表示这个节点可以表示的前缀个数，后缀个数，区间个数，以及这个节点是否被ban掉
合并两个孩子的转移式子自己手推一下就行了
如果一个节点所在的子树中没有任何节点被ban掉，那么这四个值都是可以快速计算的，因此我们写个动态开点线段树这题就完了
复杂度$O(mlogn)$
上代码~
```C
// luogu-judger-enable-o2
#include<cstdio>
#include<algorithm>
using namespace std;const int N=1e5+10;typedef long long ll;
const ll mod=998244353;ll n;int m;
#define md(x) (x=(x>mod)?x-mod:x)
#define ctwo(x) (((ll)x*(x-1)/2+x)%mod)
#define dec(x) (x=x?x-1:mod-1)
#define inc(x) (x=(x==mod-1)?0:x+1)
struct data
{
int ans;int pre;int suf;int iso;
data(){ans=pre=suf=iso=0;}
data(ll len){ans=ctwo(len);pre=len;suf=len;iso=1;}
};
inline void mg(data& p,const data& p1,const data& p2)
{
p.pre=p1.pre+p1.iso*p2.pre;md(p.pre);
p.suf=p2.suf+p2.iso*p1.suf;md(p.suf);
p.ans=(p1.ans+p2.ans+(ll)p1.suf*p2.pre)%mod;
if(p.iso){if(!(p1.iso&&p2.iso))inc(p.pre),inc(p.suf),inc(p.ans);}
else if(p1.iso&&p2.iso)dec(p.pre),dec(p.suf),dec(p.ans);
}
struct linetree
{
data dp[100*N];int s[100*N][2];int ct;
inline void ud(int p,int p1,int p2,ll le1,ll le2)
{
if(le1==0){dp[p]=data();return;}data c1=p1?dp[p1]:data(le1%mod);
data c2=p2?dp[p2]:data(le2%mod);mg(dp[p],c1,c2);
}
inline void modify(int p,ll l,ll r,ll dl,ll dr)
{
if(dl==l&&dr==r)
{
// printf("ban %lld %lld\n",l,r);
dp[p].iso=0;ud(p,s[p][0],s[p][1],(r-l)>>1,(r-l+1)>>1);
// printf("dp[%lld,%lld]=%d,%d,%d\n",l,r,dp[p].ans,dp[p].pre,dp[p].suf);
return;
}
ll mid=(l+r)>>1;
if(dl<mid)
{
if(s[p][0]==0)s[p][0]=++ct,dp[ct]=data((mid-l)%mod);
modify(s[p][0],l,mid,dl,min(dr,mid));
}
if(mid<dr)
{
if(s[p][1]==0)s[p][1]=++ct,dp[ct]=data((r-mid)%mod);
modify(s[p][1],mid,r,max(dl,mid),dr);
}ud(p,s[p][0],s[p][1],mid-l,r-mid);
// printf("dp[%lld,%lld]=%d,%d,%d\n",l,r,dp[p].ans,dp[p].pre,dp[p].suf);
}
}lt;
int main()
{
//freopen("sample1.txt","r",stdin);//freopen("tst10.out","w",stdout);
scanf("%lld%d",&n,&m);lt.dp[++lt.ct]=data(n%mod);ll l;ll r;
for(int i=1;i<=m;i++)scanf("%lld%lld",&l,&r),lt.modify(1,0,n,l-1,r);
printf("%d",lt.dp[1].ans);return 0;
}
```
### C:
~~梗:字符集是yuzusoft~~
这题比上一道题还好写
观察到两个字符串lcp长度大于等于k当且仅当他们的前k个字符相等，因此我们把所有长度恰好为k的字符串hash出来就成了小z的袜子了，大力莫队即可
蛤？莫队复杂度是$O(n\sqrt{n})$的过不去？标准莫队是将块长设为$\frac{n}{\sqrt{m}}$此时的复杂度是$O(n\sqrt{m})$的了解一下，这也是为什么这题保证了$O(n^2m)$不会很大的原因
为了给后缀数据结构学傻的同学~~(比如出题人)~~一丝活路，这题很良心的没有卡sam，但是卡了倍增的后缀数组，这两个做法大概也是相同的思路
我标算写的是sam，~~因为这样不用担心被hack~~
复杂度$O(\Sigma N+N\sqrt{m})$或者是$O(NlogN+N\sqrt{m})$或者是肥肠强的$O(n+n\sqrt{m})$(会sais的巨佬写的后缀数组)或者是$O(N+N\sqrt{m})$(用hash表写的离散化)
上代码~
```C
// luogu-judger-enable-o2
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;const int N=3*1e6+10;const int M=1e5+10;int B;typedef long long ll;
int col[N];char mde[N];int n;int m;int k;int trs[130];
struct suffixautomaton
{
int mp[2*N][10];int ed;int ct;int len[2*N];int fa[2*N];
int v[2*N];int x[2*N];int ctt;int al[2*N];int df;
inline void add(int u,int V){v[++ctt]=V;x[ctt]=al[u];al[u]=ctt;}
inline void build(){for(int i=1;i<=ct;i++)add(fa[i],i);}
inline void ih(){ed=n+1;ct=n+1;for(int i=1;i<=n;i++)len[i]=i;}
inline void ins(int c,int i)
{
//printf("ins %d\n",i);
int p=ed;for(ed=i;p&&!mp[p][c];p=fa[p])mp[p][c]=i;
if(p==0){fa[i]=n+1;return;}int q=mp[p][c];
if(len[q]==len[p]+1){fa[i]=q;return;}++ct;len[ct]=len[p]+1;
for(int i=1;i<=7;i++)mp[ct][i]=mp[q][i];
for(;p&&mp[p][c]==q;p=fa[p])mp[p][c]=ct;
fa[ct]=fa[q];fa[i]=ct;fa[q]=ct;
}
inline void dfs(int u,int co)
{
if(u<=n)col[u]=co;if(co!=0)for(int i=al[u];i;i=x[i])dfs(v[i],co);
else for(int i=al[u];i;i=x[i])if(len[v[i]]>=k)dfs(v[i],++df);else dfs(v[i],0);
}
}sam;int cnt[N];ll ans[M];ll nans;struct qry{int l;int r;int t;}qr[M];
inline void ins(int x){x=col[x];if(x){nans+=cnt[x];cnt[x]++;}}
inline void del(int x){x=col[x];if(x){cnt[x]--;nans-=cnt[x];}}
inline bool cmp1(const qry& a,const qry& b){return a.l<b.l;}
inline bool cmp2(const qry& a,const qry& b){return a.r<b.r;}
int main()
{
//freopen("tst9.in","r",stdin);//freopen("tst9.out","w",stdout);
trs['y']=1;trs['u']=2;trs['z']=3;trs['s']=4;trs['o']=5;trs['f']=6;trs['t']=7;
scanf("%d%d%d",&n,&m,&k);scanf("%s",mde+1);sam.ih();B=max((int)(n/(sqrt(m)+1)),1);
for(int i=n,j=1;i>=1;i--,j++)sam.ins(trs[mde[i]],j);sam.build();sam.dfs(n+1,(k==0));
for(int i=1;i<=n/2;i++)swap(col[i],col[n-i+1]);
for(int i=1;i<=m;i++)scanf("%d%d",&qr[i].l,&qr[i].r),qr[i].t=i;
sort(qr+1,qr+m+1,cmp1);
for(int i=1,j=0;i<=n;i+=B)
{int p=j;while(j!=m&&qr[j+1].l<i+B)j++;if(p!=j)sort(qr+p+1,qr+j+1,cmp2);}
for(int i=1,dl=0,dr=0;i<=m;i++)
{
while(dl<qr[i].l)del(dl),++dl;while(dl>qr[i].l)--dl,ins(dl);
while(dr<qr[i].r)++dr,ins(dr);while(dr>qr[i].r)del(dr),--dr;
ans[qr[i].t]=nans;
}for(int i=1;i<=m;i++)printf("%lld\n",ans[i]);return 0;
}
```
### D:
~~梗:宁宁天下第一~~
由于$\text{zhoutb2333}$花了$3ms$秒了E题和F题，所以这题可能是本场最难的题了
然而做这道题不需要任何前置芝士，我们唯一需要的就是普及组就在考的**栈,排序和双指针**
这个出题人过于菜了以至于他只会一个时空复杂度都是$O(n\sqrt{n})$的垃圾做法，欢迎log做法的聚聚爆踩他~
让我们先来想一个相当trival的$O(nlogn\sqrt{n})$的做法
每个块维护一个堆或者是set,存储覆盖这个块的所有操作，每个散点维护一个堆或者是set，存储覆盖这个块的所有操作，这样的话我们可以非常方便的得知每个点和每个块上正在生效的赋值操作是谁
然后我们将块内中的每个点按照最后有效操作时间排序，那么一个块的和就可以这样快速的求出来
二分出来那些点的生效时间在块的生效时间之后，假设这些点的和为a，然后还可以得到有几个点颜色被块上的修改所覆盖了，设这些点的个数为b，那么块中元素的和就是$kb+a$,如果k是块上的数字大小的话
好了现在我们通过了20%的数据啦~
现在考虑怎么把log卡下来
首先我们发现set或者是堆这种东西实在是太蠢了，其实我们用一个栈就可以起到相同的效果咯~我们每次检查一下栈顶，如果栈顶被删除了就pop栈顶直到栈顶未被删除即可，这样插入的时间复杂度就是$O(1)$了
接下来我们需要把排序的log卡下来，观察排序的数字值域是$O(m)$级别的，我们把每个数字看成$O(\sqrt{m})$进制的数字跑个基数排序复杂度就是$O(\sqrt{M})$了，当然我们的赋值操作不超过65536因此可以使用256进制规避掉取模~~(叫我duliu)~~
接下来我们需要把二分的log卡下来，我们发现如果块的栈顶元素是在重构之后push的话整个块将会是一个值，否则栈顶就是重构之前的最大值，而显然重构之前的最大值是单调不增的，维护一个指针每次暴力向左爬即可~
上代码~
```C
// luogu-judger-enable-o2
// luogu-judger-enable-o2
// luogu-judger-enable-o2
// luogu-judger-enable-o2
// luogu-judger-enable-o2
#include<cstdio>
#include<algorithm>
using namespace std;
//const int N=1e4+10;const int B=50;
//const int N=1e2+10;const int B=5;
const int N=1e5+10;const int B=290;
template <class T>
void read(T &x){
char c;
bool op = 0;
while(c = getchar(), c < '0' || c > '9')
if(c == '-') op = 1;
x = c - '0';
while(c = getchar(), c >= '0' && c <= '9')
x = x * 10 + c - '0';
if(op) x = -x;
}
typedef long long ll;
bool mrk[N];int ql[N];int qr[N];int qv[N];int cnt;int Pl[N/B+3];int Pr[N/B+3];
int bi[N];int bj[N];int n;int m;int a[N];int sum[260];int tr[B];
namespace lis
{
int al[N];int x[N*B];int v[N*B];int ct;
inline void pb(const int& u,const int& V){v[++ct]=V;x[ct]=al[u];al[u]=ct;}
inline void pop(const int& u){while(mrk[v[al[u]]])al[u]=x[al[u]];}
inline int gt(const int& x){return v[al[x]];}
}
struct blk
{
int st[N];int tp;int lst;int vt[B+3];//int p1;
int p2;
ll ans[B+3];int siz;ll ret;int a[B+3];int dl;
inline int& operator [](const int& x){return a[x];}
inline ll rixs()
{
ll ans=0;
for(int i=1;i<=siz;++i)vt[i]=lis::gt(dl+i),ans+=(vt[i])?0:a[i];
for(int i=0;i<256;++i)sum[i]=0;
for(int i=1;i<=siz;++i)sum[vt[i]&255]++;
for(int i=1;i<256;++i)sum[i]+=sum[i-1];
for(int i=siz;i>=1;--i)tr[sum[vt[i]&255]--]=vt[i];int lim=cnt>>8;
for(int i=0;i<=lim;++i)sum[i]=0;
for(int i=1;i<=siz;++i)sum[vt[i]>>8]++;
for(int i=1;i<=lim;++i)sum[i]+=sum[i-1];
for(int i=siz;i>=1;--i)vt[sum[tr[i]>>8]--]=tr[i];return ans;
}
inline void rebuild()
{
ll trp=rixs();//lst=st[tp]>>10;
lst=st[tp];
for(int i=siz-1;i>=0;i--)ans[i]=ans[i+1]+qv[vt[i+1]];ans[0]+=trp;
p2=0;while(p2!=siz&&vt[p2+1]<lst)p2++;
// p1=0;while(p1!=siz&&vt[p1+1]<cnt)p1++;
ret=ans[p2]+(ll)p2*qv[lst];
}
inline void build(){for(int i=1;i<=siz;i++)ans[0]+=a[i];ret=ans[0];}
inline void ins()
{
//while(p1!=siz&&vt[p1+1]<cnt)p1++;
st[++tp]=cnt;ret=(ll)siz*qv[cnt];
}
inline void del()
{
while(mrk[st[tp]])tp--;int tv=st[tp];
if(tv<=lst){while(p2&&vt[p2]>=tv)p2--;ret=ans[p2]+(ll)p2*qv[tv];}
else ret=(ll)siz*qv[tv];
}
inline ll brucalc(int l,int r)
{
int tv=st[tp];int va=qv[tv];ll rea=0;
if(tv==0)for(int i=l;i<=r;i++)rea+=(lis::gt(i))?qv[lis::gt(i)]:a[i-dl];
else for(int i=l;i<=r;i++)rea+=(lis::gt(i)<tv)?va:qv[lis::gt(i)];
return rea;
}
}bl[N/B+3];
inline void modify(int l,int r)
{
if(bi[l]==bi[r])
{for(int i=l;i<=r;i++)lis::pb(i,cnt);bl[bi[l]].rebuild();return;}
int p1=bi[l];int p2=bi[r];
for(int i=l;bi[i]==p1;i++)lis::pb(i,cnt);bl[p1].rebuild();
for(int i=r;bi[i]==p2;i--)lis::pb(i,cnt);bl[p2].rebuild();
for(int i=p1+1;i<p2;i++)bl[i].ins();
}
inline void del(int l,int r)
{
if(bi[l]==bi[r])
{for(int i=l;i<=r;i++)lis::pop(i);bl[bi[l]].rebuild();return;}
int p1=bi[l];int p2=bi[r];
for(int i=l;bi[i]==p1;i++)lis::pop(i);bl[p1].rebuild();
for(int i=r;bi[i]==p2;i--)lis::pop(i);bl[p2].rebuild();
for(int i=p1+1;i<p2;i++)bl[i].del();
}
inline ll qry(int l,int r)
{
if(bi[l]==bi[r])return bl[bi[l]].brucalc(l,r);
int p1=bi[l];int p2=bi[r];ll ret=0;
ret+=bl[p1].brucalc(l,Pr[p1]);ret+=bl[p2].brucalc(Pl[p2],r);
for(int i=p1+1;i<p2;i++)ret+=bl[i].ret;return ret;
}
int main()
{
//system("fc tst1.ck tst1.out");
//freopen("tst10.in","r",stdin);freopen("tst10.ck","w",stdout);
//freopen("tst.txt","r",stdin);freopen("std.txt","w",stdout);
// freopen("sample1.txt","r",stdin);freopen("sampleans1.txt","w",stdout);
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)bi[i]=(i-1)/B+1;for(int i=1;i<=n;i++)bj[i]=(i-1)%B+1;
for(int i=1;i<=n;i++)Pr[bi[i]]=i;for(int i=n;i>=1;i--)Pl[bi[i]]=i;
for(int i=1;i<=n;i++)read(bl[bi[i]][bj[i]]);
for(int i=1;i<=bi[n];i++)bl[i].dl=Pl[i]-1,bl[i].siz=B;bl[bi[n]].siz=(n%B)?n%B:B;
for(int i=1;i<=bi[n];i++)bl[i].build();ll l;ll r;ll x;ll lastans=0;
for(int i=1,tp;i<=m;i++)
{
//if(i%1000==0){printf("deal %d\n",i);}
read(tp);
switch(tp)
{
case 1:
{
++cnt,
read(l);read(r);read(qv[cnt]);ql[cnt]=l^lastans;qr[cnt]=r^lastans;
//read(ql[cnt]),read(qr[cnt]),read(qv[cnt]),
modify(ql[cnt],qr[cnt]);
break;
}
case 2:
{
read(l);read(r);l^=lastans;r^=lastans;
lastans=qry(l,r);printf("%lld\n",lastans);
// printf("%lld\n",qry(l,r));
break;
}
case 3:{read(x);x^=lastans;mrk[x]=true;del(ql[x],qr[x]);break;}
}
}
// printf("ct=%d,cnt=%d,%d\n",lis::ct,cnt,N*B);
return 0;
}
```
### E:
~~边分治，闵可夫斯基和，然后在凸包上二分~~
~~我相信如果您看懂了上面在说什么就写的出来，否则可能你就算知道了标算是什么可能也没有写下来的勇气了~~
观察到题中所给的式子就是一个二维线性规划的式子
那么我们事实上仅仅需要搞一个凸包x坐标就是路径a属性的和，y坐标就是路径b属性的和,然后在凸包上面二分斜率找最优解就行了
接下来我们就是如果求出来这个凸包的问题了，考虑边分治求这个凸包，然后我们在边分治的每一层合并黑点凸包和白点凸包就行了
注意一件事情是多叉树转二叉树会丢掉lca，此时我们需要手动把lca补上去
上代码~
```C
// luogu-judger-enable-o2
#include<cstdio>
#include<algorithm>
using namespace std;const int N=2*1e5+10;typedef long long ll;
struct poi
{
ll x;ll y;
friend poi operator +(poi a,poi b){return (poi){a.x+b.x,a.y+b.y};}
friend poi operator -(poi a,poi b){return (poi){a.x-b.x,a.y-b.y};}
friend bool operator <(poi a,poi b){return a.y*b.x<b.y*a.x;}
friend bool operator <(ll k,poi a){return k*a.x<a.y;}
}ans[40*N],d1w[N],d2w[N],d1b[N],d2b[N],dis[N];int tp;int t1w;int t2w;int t1b;int t2b;
inline bool cmp(const poi& a,const poi& b){return (a.x==b.x)?a.y>b.y:a.x<b.x;}
inline void chull(poi* a,int& tp)
{
sort(a+1,a+tp+1,cmp);
int lim=tp;tp=1;for(int i=2;i<=lim;i++)
if(a[i].x!=a[tp].x){while(tp>1&&(a[tp]-a[tp-1])<(a[i]-a[tp-1]))tp--;a[++tp]=a[i];}
}
inline void hull_merge(poi* a1,int& tp1,poi* a2,int& tp2)
{
if(tp1==0||tp2==0)return;chull(a1,tp1);chull(a2,tp2);ans[++tp]=a1[1]+a2[1];
int i=1;int j=1;while(i!=tp1&&j!=tp2)
{((a2[j+1]-a2[j]<a1[i+1]-a1[i])?i:j)++;ans[++tp]=a1[i]+a2[j];}
if(i!=tp1)for(i++;i<=tp1;i++)ans[++tp]=a1[i]+a2[j];
if(j!=tp2)for(j++;j<=tp2;j++)ans[++tp]=a1[i]+a2[j];
}
inline ll calc(ll k)
{
int l=1;int r=tp;
while(l!=r){int mid=(l+r)/2;if(k<(ans[mid+1]-ans[mid]))l=mid+1;else r=mid;}
return ans[l].x*(-k)+ans[l].y;
}
int v[2*N];int x[2*N];int ct=1;int al[N];int col[N];ll wa[N];ll wb[N];
int siz[N];bool cut[2*N];int q[N];int hd;int dep[N];int n;int m;
inline void add(int u,int V){v[++ct]=V;x[ct]=al[u];al[u]=ct;}
namespace oldtree
{
int v[N];int x[N];int ct;int al[N/2];int fa[N];int lst[N];int ctt;
inline void ins(int u,int V){v[++ct]=V;x[ct]=al[u];al[u]=ct;}
inline void dfs(int u)
{for(int i=al[u];i;i=x[i])if(v[i]!=fa[u])fa[v[i]]=u,dfs(v[i]);}
inline void build()
{
dfs(1);for(int i=1;i<=n;i++)lst[i]=i;ctt=n;
for(int i=2;i<=n;i++)
{
int nu=lst[fa[i]];++ctt;add(ctt,nu);add(nu,ctt);add(ctt,i);
add(i,ctt);wa[ctt]=wa[nu];wb[ctt]=wb[nu];lst[fa[i]]=ctt;
}
}
}
inline void pdfs(int u,int f)
{dep[u]=dep[f]+1;for(int i=al[u];i;i=x[i])if(v[i]!=f)pdfs(v[i],u);}
inline int dfs1(int u,int f)
{siz[u]=1;for(int i=al[u];i;i=x[i])if(v[i]!=f&&!cut[i])q[++hd]=i,siz[u]+=dfs1(v[i],u);return siz[u];}
inline void dfs2(int u,int f,poi* a1,int& tp1,poi* a2,int& tp2)
{
if(u<=n)
{
dis[u]=dis[f]+(poi){wa[u],wb[u]};
if(col[u]==0)a1[++tp1]=dis[u];else a2[++tp2]=dis[u];
}else dis[u]=dis[f];
for(int i=al[u];i;i=x[i])if(v[i]!=f&&!cut[i])dfs2(v[i],u,a1,tp1,a2,tp2);
}
inline void dfs3(int u,int f,poi* a1,int& tp1,poi* a2,int& tp2,int lc)
{
lc=dep[lc]>dep[u]?u:lc;
if(u<=n)
{
dis[u]=dis[f]+(poi){wa[u],wb[u]};poi bn=(lc>n)?(poi){wa[lc],wb[lc]}:(poi){0,0};
if(col[u]==0)a1[++tp1]=dis[u]+bn;else a2[++tp2]=dis[u]+bn;
}else dis[u]=dis[f];
for(int i=al[u];i;i=x[i])if(v[i]!=f&&!cut[i])dfs3(v[i],u,a1,tp1,a2,tp2,lc);
}
inline void solve(int u)
{
hd=0;dfs1(u,0);if(siz[u]==1)return;int misiz=0x3f3f3f3f;int ce=0;
for(int i=1;i<=hd;i++)
{int nv=max(siz[v[q[i]]],siz[u]-siz[v[q[i]]]);if(nv<misiz)ce=q[i],misiz=nv;}
cut[ce]=true;cut[ce^1]=true;t1w=0;t1b=0;t2w=0;t2b=0;int v1=v[ce];int v2=v[ce^1];
if(dep[v1]<dep[v2])swap(v1,v2);
dfs2(v1,0,d1w,t1w,d1b,t1b);dfs3(v2,0,d2w,t2w,d2b,t2b,v2);
hull_merge(d1w,t1w,d2b,t2b);hull_merge(d2w,t2w,d1b,t1b);solve(v1);solve(v2);
}
int main()
{
//freopen("tst15.in","r",stdin);freopen("tst15.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%lld",&wa[i]);
for(int i=1;i<=n;i++)scanf("%lld",&wb[i]);
for(int i=1;i<=n;i++)scanf("%d",&col[i]);
for(int i=1,u,v;i<n;i++){scanf("%d%d",&u,&v);oldtree::ins(u,v);oldtree::ins(v,u);}
oldtree::build();pdfs(1,0);solve(1);
chull(ans,tp);ans[tp+1].x=ans[tp].x;ans[tp+1].y=-0x3f3f3f3f;
for(int i=1;i<=m;i++){ll nk;scanf("%lld",&nk);printf("%lld\n",calc(-nk));}
return 0;
}
```
### F:
这题最早是$\text{zhoutb2333}$出的，但是当时没有k1的限制而k2也非常小，只有20，然后我稍稍加强了一下这题
那么我们这种题显然是sam咯~
相信诸位在写sam上跑线段树合并的题已经相当熟练辣~
所以这题我的写法是在sam上跑边分树合并~
首先我们正着跑一遍sam然后反着跑一遍sam，根据parent树的一些性质我们可以知道两个前缀节点的lcs是这两个节点lca的len值，同理两个后缀节点的lcp是这两个节点lca的len值，那么我们如果把第一棵树大于k1的len置为0，第二棵数大于k2的len置为0的话，问题就转化为了给你两棵树，然后询问所有点对在两颗树上的lca的len值之积
那么我们考虑在第一棵树上dfs枚举lca然后考虑这个点对答案的贡献
那么我们可以一个一个的合并这个lca的每一个子树，然后考虑求出跨越两个联通块的点对在第二棵树上的lca的len值之和
这个东西可以边分树合并爆搞一下，具体点来讲我们将深度较低的一个联通块看成是右儿子而深度较大的一个联通块看成左儿子，然后每一个边分树节点维护一下左儿子中的节点个数和右儿子联通块中可能成为lca节点的点权和，然后合并的时候相乘一下就可以统计贡献啦~
代码十分好写~
```C
// luogu-judger-enable-o2
#include<cstdio>
#include<algorithm>
using namespace std;const int N=1e5+10;typedef unsigned long long ll;
int n;char mde[N];ll len[N<<2];ll lw[N<<1];int mxc;ll ans;int a;int b;
namespace lt
{
int s[60*N][2];ll vl[60*N];ll vr[60*N];int ct;
inline ll mg(int p1,int p2)
{
ll ret=0;
if(s[p1][0]&&s[p2][0])ret+=mg(s[p1][0],s[p2][0]);else if(s[p2][0])s[p1][0]=s[p2][0];
if(s[p1][1]&&s[p2][1])ret+=mg(s[p1][1],s[p2][1]);else if(s[p2][1])s[p1][1]=s[p2][1];
ret+=vl[p1]*vr[p2]+vl[p2]*vr[p1];vl[p1]+=vl[p2];vr[p1]+=vr[p2];return ret;
}
inline int ins(int p,int tp,ll l,ll r){vl[p]=l;vr[p]=r;s[p][tp]=++ct;return ct;}
}
namespace Tree1
{
int v[N<<3];int x[N<<3];int al[N<<2];int ct=1;int siz[N<<2];
int ge;int gv;bool cut[N<<3];int dep[N<<2];int hd[N];int fa[N<<2];
inline void add(int u,int V){v[++ct]=V;x[ct]=al[u];al[u]=ct;}
inline int dfs1(int u,int f)
{siz[u]=1;for(int i=al[u];i;i=x[i])if(v[i]!=f&&!cut[i])siz[u]+=dfs1(v[i],u);return siz[u];}
inline void find(int u,int f,const int& tot)
{
int tv=max(siz[u],tot-siz[u]);if(tv<gv)gv=tv,ge=f;
for(int i=al[u];i;i=x[i])if(i!=(f^1)&&!cut[i])find(v[i],i,tot);
}
inline void dfs3(int u,int f)
{
if(u<=n)hd[u]=lt::ins(hd[u],0,1,0);
for(int i=al[u];i;i=x[i])if(v[i]!=f&&!cut[i])dfs3(v[i],u);
}
inline void dfs4(int u,int f,const ll& w)
{
if(u<=n)hd[u]=lt::ins(hd[u],1,0,w);
for(int i=al[u];i;i=x[i])if(v[i]!=f&&!cut[i])dfs4(v[i],u,w);
}
inline void solve(int u)
{
dfs1(u,0);if(siz[u]==1)return;gv=0x3f3f3f3f;find(u,0,siz[u]);cut[ge]=true;cut[ge^1]=true;
int st=v[ge];int ed=v[ge^1];if(dep[ed]>dep[st])swap(st,ed);dfs3(st,ed);
for(int p=ed,lst=st;;lst=p,p=v[fa[p]])
{
for(int i=al[p];i;i=x[i])if(!cut[i]&&i!=fa[p]&&v[i]!=lst)dfs4(v[i],p,len[p]);
if(p<=n)hd[p]=lt::ins(hd[p],1,0,len[p]);if(cut[fa[p]])break;
}solve(st);solve(ed);
}
inline void pre(int u)
{for(int i=al[u];i;i=x[i])if(i!=fa[u])dep[v[i]]=dep[u]+1,fa[v[i]]=i^1,pre(v[i]);}
inline void ih(){for(int i=1;i<=n;i++)hd[i]=i;cut[0]=true;pre(n+1);}
}
namespace Ot
{
int hd[N];int tot;
# define add(u,v) Tree1::add(u,v)
inline void ih(){tot=mxc;for(int i=1;i<=mxc;i++)hd[i]=i;}
inline void ins(int u,int f)
{++tot;add(tot,hd[f]),add(hd[f],tot),hd[f]=tot,len[tot]=len[f];add(u,tot),add(tot,u);}
# undef add
}
int al[N<<1];int x[N<<1];int v[N<<1];int ct;
inline void add(int u,int V){v[++ct]=V;x[ct]=al[u];al[u]=ct;}
inline int dfs(int u)
{
int ret=(u<=n)?u:0;
for(int i=al[u];i;i=x[i])
{int vp=dfs(v[i]);if(ret==0)ret=vp;else if(vp)ans+=lw[u]*lt::mg(ret,vp);}
return ret;
}
namespace sam
{
int mp[N<<1][28];int ct;ll* len;int fa[N<<1];
inline void clr()
{
for(int i=1;i<=ct;i++)fa[i]=0;
for(int i=1;i<=ct;i++)for(int j=1;j<=26;j++)mp[i][j]=0;ct=n+1;
}
inline void ins(int nw,int ed,int c)
{
len[nw]=len[ed]+1;int p=ed;
for(;mp[p][c]==0&&p;p=fa[p])mp[p][c]=nw;
if(p==0){fa[nw]=n+1;return;}int q=mp[p][c];
if(len[q]==len[p]+1){fa[nw]=q;return;}len[++ct]=len[p]+1;
for(int i=1;i<=26;i++)mp[ct][i]=mp[q][i];
for(;mp[p][c]==q&&p;p=fa[p])mp[p][c]=ct;
fa[ct]=fa[q];fa[q]=fa[nw]=ct;
}
}
int main()
{
scanf("%s",mde+1);scanf("%d%d",&a,&b);for(n=1;mde[n+1]!='\0';n++);
sam::ct=n+1;sam::len=len;lt::ct=n;
for(int p=n+1,i=1;i<=n;p=i,i++)sam::ins(i,p,mde[i]-'a'+1);mxc=sam::ct;
for(int i=1;i<=mxc;i++)len[i]=((len[i]<=b)?len[i]:0);Ot::ih();
for(int i=1;i<=mxc;i++)if(i!=n+1)Ot::ins(i,sam::fa[i]);Tree1::ih();Tree1::solve(n+1);
sam::clr();sam::len=lw;
for(int p=n+1,i=n;i>=1;p=i,i--)sam::ins(i,p,mde[i]-'a'+1);
for(int i=1;i<=sam::ct;i++)if(i!=n+1)add(sam::fa[i],i);
for(int i=1;i<=sam::ct;i++)lw[i]=((lw[i]<=a)?lw[i]:0);
dfs(n+1);printf("%llu",ans);return 0;
}
```