我是 sb。T1 线段树 update 写挂挂成 70。
某种程度上提前看题确实没什么用，会的都会不会的还是不会。
游戏
签到题。我没签上到是不是可以走了。
首先我们只关心每个点往外最长的三条链。这个可以换根搞。设三条链从大到小为 \(a,b,c\)。那么每个询问我们就需要找一个点，满足这个点到三个点 \((x,y,z)\) 的距离是某个数（这三个距离可以根据给的三个数解个方程得到）。不妨设 \(x\ge y\ge z\)，那么我们就需要找到一个点满足 \(x\le a,y\le b,z\le c\)。三维偏序，但是只要一组方案。
这个很好搞，第一维塞进桶倒着扫，第二维线段树下标，第三维区间最大值。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
int n,Q,ans[200010];
struct gra{
int v,next;
}edge[400010];
int t,head[200010];
void add(int u,int v){
edge[++t].v=v;edge[t].next=head[u];head[u]=t;
}
pair<int,int>mx[200010][3];
vector<int>od[200010];
int dep[200010],fa[200010][20];
void dfs1(int x,int f){
dep[x]=dep[f]+1;
int son=0;
for(int i=0;i<3;i++)mx[x][i]=make_pair(0,x);
for(int i=head[x];i;i=edge[i].next){
if(edge[i].v!=f){
son++;
fa[edge[i].v][0]=x;
for(int j=1;j<20;j++)fa[edge[i].v][j]=fa[fa[edge[i].v][j-1]][j-1];
dfs1(edge[i].v,x);
pair<int,int>k=mx[edge[i].v][0];k.first++;
for(int j=0;j<3;j++)if(k.first>=mx[x][j].first)swap(k,mx[x][j]);
}
}
}
void dfs2(int x,int f,pair<int,int>k){
for(int i=0;i<3;i++)if(k.first>=mx[x][i].first)swap(k,mx[x][i]);
for(int i=head[x];i;i=edge[i].next){
if(edge[i].v!=f){
pair<int,int>ret;
if(mx[x][0].second==mx[edge[i].v][0].second)ret=mx[x][1];
else ret=mx[x][0];
ret=max(ret,k);
ret.first++;
dfs2(edge[i].v,x,ret);
}
}
}
int lca(int x,int y){
if(dep[x]>dep[y])swap(x,y);
for(int i=19;i>=0;i--)if(dep[fa[y][i]]>=dep[x])y=fa[y][i];
if(x==y)return x;
for(int i=19;i>=0;i--)if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];
return fa[x][0];
}
int dis(int x,int y){
return dep[x]+dep[y]-2*dep[lca(x,y)];
}
int getkth(int x,int y,int k){
int lc=lca(x,y);
if(k>dep[x]-dep[lc]){
k=dep[x]+dep[y]-2*dep[lc]-k;
x=y;
}
for(int i=19;i>=0;i--)if(dep[x]-dep[fa[x][i]]<=k)k-=dep[x]-dep[fa[x][i]],x=fa[x][i];
return x;
}
struct Ques{
int x,y,z;
}ques[200010];
vector<pair<int,int> >q[200010];
#define lson rt<<1
#define rson rt<<1|1
int tree[800010];
void pushup(int rt){
if(mx[tree[lson]][2].first>=mx[tree[rson]][2].first)tree[rt]=tree[lson];
else tree[rt]=tree[rson];
}
void update(int rt,int L,int R,int pos,int x){
if(L==R){
if(mx[x][2].first>=mx[tree[rt]][2].first)tree[rt]=x;
return;
}
int mid=(L+R)>>1;
if(pos<=mid)update(lson,L,mid,pos,x);
else update(rson,mid+1,R,pos,x);
pushup(rt);
}
int query(int rt,int L,int R,int l,int r){
if(l<=L&&R<=r)return tree[rt];
int mid=(L+R)>>1,val=0;
if(l<=mid){
int ret=query(lson,L,mid,l,r);
if(!val||mx[val][2].first<mx[ret][2].first)val=ret;
}
if(mid<r){
int ret=query(rson,mid+1,R,l,r);
if(!val||mx[val][2].first<mx[ret][2].first)val=ret;
}
return val;
}
bool check(int x,int y,int z,int u,int v,int w,int p){
return dis(p,u)==x&&dis(p,v)==y&&dis(p,w)==z;
}
int main(){
scanf("%d",&n);
for(int i=1;i<n;i++){
int u,v;scanf("%d%d",&u,&v);
add(u,v);add(v,u);
}
dfs1(1,0);dfs2(1,0,make_pair(0,0));
for(int i=1;i<=n;i++)od[mx[i][0].first].push_back(i);
scanf("%d",&Q);
static int tmp[3];
for(int i=1;i<=Q;i++){
int x,y,z;scanf("%d%d%d",&x,&y,&z);
tmp[0]=(x+y-z)>>1;
tmp[1]=(x-y+z)>>1;
tmp[2]=(-x+y+z)>>1;
ques[i]={tmp[0],tmp[1],tmp[2]};
sort(tmp,tmp+3);
q[tmp[2]].push_back(make_pair(i,tmp[1]));
}
for(int i=n;i>=0;i--){
for(int x:od[i])update(1,0,n,mx[x][1].first,x);
for(pair<int,int> p:q[i])ans[p.first]=query(1,0,n,p.second,n);
}
for(int i=1;i<=Q;i++){
int p=ans[i];
tmp[0]=ques[i].x,tmp[1]=ques[i].y,tmp[2]=ques[i].z;sort(tmp,tmp+3);
int u=getkth(p,mx[p][0].second,tmp[2]),v=getkth(p,mx[p][1].second,tmp[1]),w=getkth(p,mx[p][2].second,tmp[0]);
if(check(ques[i].x,ques[i].y,ques[i].z,u,v,w,p))printf("%d %d %d\n",u,v,w);
else if(check(ques[i].x,ques[i].y,ques[i].z,u,w,v,p))printf("%d %d %d\n",u,w,v);
else if(check(ques[i].x,ques[i].y,ques[i].z,v,u,w,p))printf("%d %d %d\n",v,u,w);
else if(check(ques[i].x,ques[i].y,ques[i].z,v,w,u,p))printf("%d %d %d\n",v,w,u);
else if(check(ques[i].x,ques[i].y,ques[i].z,w,u,v,p))printf("%d %d %d\n",w,u,v);
else if(check(ques[i].x,ques[i].y,ques[i].z,w,v,u,p))printf("%d %d %d\n",w,v,u);
}
return 0;
}
马戏团里你最忙
神秘题。
首先有一个暴力：设 \(f_{i,j},g_{i,j}\) 分别为第 \(i\) 次操作之后为 \(j\) 的概率和到 \(j\) 的答案，转移 FWT 一下。
然后根据我不知道为什么的人类智慧，这个答案满足线性递推，即 \(g_i=\sum_{j=1}^mg_{i-j}a_{j-1}\)，\(a\) 是常数，也就是每位互不影响。那暴力出前面若干位（这题数据线性递推长度最长 \(36\)，所以大概处理 \(75\) 位就行），然后为了方便（不用一位一位乘数组）对 \(0-2^n-1\) 的每一位整个随机值作为权值然后加起来，相当于哈希一下。由于每一位互不影响所以这个不影响答案。这样我们得到了一个数组，对它跑 BM 就得到线性递推，然后矩阵乘一下就行了。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <cmath>
#include <vector>
#include <random>
using namespace std;
const int mod=998244353,inv2=(mod+1)>>1;
int n,m,P,k,x0,f[80][1<<17],g[80][1<<17],c[1<<17];
int qpow(int a,int b){
int ans=1;
while(b){
if(b&1)ans=1ll*ans*a%mod;
a=1ll*a*a%mod;
b>>=1;
}
return ans;
}
void getor(int a[],int n,int tp){
for(int mid=1;mid<n;mid<<=1){
for(int i=0;i<n;i+=mid<<1){
for(int j=0;j<mid;j++){
a[i+j+mid]=(a[i+j+mid]+1ll*tp*a[i+j])%mod;
}
}
}
}
void getand(int a[],int n,int tp){
for(int mid=1;mid<n;mid<<=1){
for(int i=0;i<n;i+=mid<<1){
for(int j=0;j<mid;j++){
a[i+j]=(a[i+j]+1ll*tp*a[i+j+mid])%mod;
}
}
}
}
struct node{
int a[80][80];
node(){memset(a,0,sizeof(a));}
node operator*(const node&s)const{
node ret;
for(int i=1;i<=m;i++)for(int j=1;j<=m;j++)for(int k=1;k<=m;k++){
ret.a[i][j]=(ret.a[i][j]+1ll*a[i][k]*s.a[k][j])%mod;
}
return ret;
}
}base;
node qpow(node a,int b){
node ans;
for(int i=1;i<=m;i++)ans.a[i][i]=1;
while(b){
if(b&1)ans=ans*a;
a=a*a;
b>>=1;
}
return ans;
}
mt19937 rnd(114514);
int p[80],rd[1<<17];
vector<int>ans;
void BM(int a[],int n,vector<int>&ans){
int w=0,del=0;
vector<int>lst;
for(int i=1;i<=n;i++){
int tmp=0;
for(int j=0;j<ans.size();j++)tmp=(tmp+1ll*a[i-j-1]*ans[j])%mod;
if((a[i]-tmp+mod)%mod==0)continue;
if(!w){
w=i;del=(a[i]-tmp+mod)%mod;
for(int j=i;j;j--)ans.push_back(0);
continue;
}
vector<int>now=ans;
int mul=1ll*(a[i]-tmp+mod)*qpow(del,mod-2)%mod;
if(ans.size()<lst.size()+i-w)ans.resize(lst.size()+i-w);
ans[i-w-1]=(ans[i-w-1]+mul)%mod;
for(int j=0;j<lst.size();j++)ans[i-w+j]=(ans[i-w+j]-1ll*mul*lst[j]%mod+mod)%mod;
if(now.size()-i<lst.size()-w){
lst=now;w=i;del=(a[i]-tmp+mod)%mod;
}
}
}
int main(){
scanf("%d%d%d%d",&n,&P,&k,&x0);
for(int i=0;i<(1<<n);i++)scanf("%d",&c[i]);
f[0][x0]=1;
m=75;
for(int t=1;t<=m;t++){
static int a[1<<17],b[1<<17];
int p1=1ll*P*qpow(inv2,n)%mod,p2=1ll*(1-P+mod)%mod*qpow(inv2,n)%mod;
for(int i=0;i<(1<<n);i++)a[i]=1ll*f[t-1][i]*p1%mod,b[i]=1ll*f[t-1][i]*p2%mod;
getor(a,1<<n,1);getand(b,1<<n,1);
for(int i=0;i<(1<<n);i++){
a[i]=1ll*a[i]*(1<<__builtin_popcount(i))%mod;
b[i]=1ll*b[i]*(1<<n-__builtin_popcount(i))%mod;
}
getor(a,1<<n,mod-1);getand(b,1<<n,mod-1);
for(int i=0;i<(1<<n);i++){
f[t][i]=(a[i]+b[i])%mod;
g[t][i]=1ll*(a[i]+b[i])%mod*c[i]%mod;
a[i]=1ll*g[t-1][i]*p1%mod;b[i]=1ll*g[t-1][i]*p2%mod;
}
getor(a,1<<n,1);getand(b,1<<n,1);
for(int i=0;i<(1<<n);i++){
a[i]=1ll*a[i]*(1<<__builtin_popcount(i))%mod;
b[i]=1ll*b[i]*(1<<n-__builtin_popcount(i))%mod;
}
getor(a,1<<n,mod-1);getand(b,1<<n,mod-1);
for(int i=0;i<(1<<n);i++)g[t][i]=(g[t][i]+1ll*a[i]+b[i])%mod;
}
for(int i=0;i<(1<<n);i++)rd[i]=rnd()%mod;
for(int i=1;i<=m;i++){
for(int j=0;j<(1<<n);j++)p[i]=(p[i]+1ll*rd[j]*g[i][j])%mod;
}
BM(p,m,ans);
m=ans.size();
for(int i=1;i<=m;i++)base.a[1][i]=ans[i-1];
for(int i=2;i<=m;i++)base.a[i][i-1]=1;
base=qpow(base,k-1);
for(int i=0;i<(1<<n);i++){
int ans=0;
for(int j=1;j<=m;j++)ans=(ans+1ll*base.a[m][j]*g[m-j+1][i])%mod;
printf("%d ",ans);
}
return 0;
}
树
挺智慧的。有不用太动脑子但是码量似乎更大的长剖做法，然而似乎不如这个巧妙。
先考虑链上怎么做。设 \(f_{i,j}\) 为 \([i,i+2^j)\) 的答案，那么转移有：
\[f_{i,j}=f_{i,j-1}+f_{i+2^{j-1},j-1}+\sum_{k=i+2^{j-1}}{i+2^j-1}2^{j-1}-2^j[(v_k>>j-1)\&1]
\]
然后前缀和一下就行了。
考虑上树。有一个非常奇妙的方法是变成如下的差分形式：每个点维护一直往最右边儿子走的同一层前缀和。如图：
此时答案就是 \(u\) 的部分减掉 \(v\) 的部分。这个东西可以类似序列上的一样维护，\(f_{x,i}\) 为从 \(x\) 往最右边儿子跳 \(2^i-1\) 步的前缀和，复杂度同样是 \(O(n\log n)\)。要预处理整个左下（子树和左边前缀）有多少个点和拆位后每一位有多少个 \(1\)，每次查询倍增跳一下儿子就行了。
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
#define int long long
using namespace std;
int n,q,ans,a[1000010],f[1000010][21];
struct gra{
int v,next;
}edge[1000010];
int t,head[1000010];
void add(int u,int v){
edge[++t].v=v;edge[t].next=head[u];head[u]=t;
}
int dep[1000010],son[1000010][21],last[1000010],pre[1000010],cnt[1000010],sum[1000010][21];
vector<int>v[1000010];
void dfs1(int x,int f){
dep[x]=dep[f]+1;
son[x][0]=last[dep[x]+1];
pre[x]=last[dep[x]];
last[dep[x]]=x;
v[dep[x]].push_back(x);
for(int i=head[x];i;i=edge[i].next){
dfs1(edge[i].v,x);
son[x][0]=edge[i].v;
}
}
void dfs2(int x){
for(int i=head[x];i;i=edge[i].next)dfs2(edge[i].v);
cnt[x]+=cnt[son[x][0]];
for(int i=0;i<=20;i++)sum[x][i]+=sum[son[x][0]][i];
}
int solve(int x,int k){
if(!x)return 0;k++;
int ans=0;
int ret=x,tmp=k;
for(int i=20;i>=0;i--){
if((1<<i)<=k){
ans+=f[x][i];x=son[x][i];k-=1<<i;
}
}
int del=x;
x=ret,k=tmp;
for(int i=20;i>=0;i--){
if((1<<i)<=k){
x=son[x][i],k-=1<<i;
ans+=(cnt[x]-cnt[del])*(1<<i)-(sum[x][i]-sum[del][i])*(1<<i+1);
}
}
return ans;
}
signed main(){
scanf("%lld",&n);dep[0]=-1;
for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
for(int i=2;i<=n;i++){
int fa;scanf("%lld",&fa);add(fa,i);
}
dfs1(1,0);
for(int d=0;d<=n;d++){
for(int i=0;i<v[d].size();i++){
int x=v[d][i];
f[x][0]=a[x];cnt[x]=1;
for(int j=0;j<=20;j++)sum[x][j]=(a[x]>>j)&1;
if(i==0)continue;
int pre=v[d][i-1];
cnt[x]+=cnt[pre];f[x][0]+=f[pre][0];
for(int j=0;j<=20;j++)sum[x][j]+=sum[pre][j];
}
}
dfs2(1);
for(int i=1;i<=20;i++){
for(int x=1;x<=n;x++){
son[x][i]=son[son[x][i-1]][i-1];
f[x][i]=f[x][i-1]+f[son[x][i-1]][i-1]+(cnt[son[x][i-1]]-cnt[son[x][i]])*(1<<i-1)-(sum[son[x][i-1]][i-1]-sum[son[x][i]][i-1])*(1<<i);
}
}
scanf("%lld",&q);
while(q--){
int x,k;scanf("%lld%lld",&x,&k);
printf("%lld\n",solve(x,k)-solve(pre[x],k));
}
return 0;
}