已经好长时间没有考试不挂分的良好体验了。。。
开场数据结构，真爽
对于这道题首先要理解对于一条链从上向下和从下向上走复活次数相等
（这可能需要晚上躺在被窝里面脑摸几种情况的样例）
然后就不难了，使用倍增，$bz[x][i]$表示节点$x$的第$2^i$级复活点位置
然后询问的话分别找到$s->lca$和$t->lca$的复活次数，是$2^i$
然后判断一下$lca$两端最后的一对复活点间的距离是否大于$k$，是的话再加一次复活
1 #include<bits/stdc++.h> 2 #define int long long 3 using namespace std; 4 namespace AE86{ 5 inline int read(){ 6 int x=0,f=1;char ch=getchar(); 7 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} 8 while(ch>=‘0‘&&ch<=‘9‘){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f; 9 }inline void write(int x,char opt=‘\n‘){ 10 char ch[20];int len=0;if(x<0)x=~x+1,putchar(‘-‘); 11 do{ch[len++]=x%10+(1<<5)+(1<<4);x/=10;}while(x); 12 for(register int i=len-1;i>=0;--i)putchar(ch[i]);putchar(opt);} 13 }using namespace AE86; 14 15 const int NN=2e5+5; 16 int n,k,q; 17 int dfn[NN],rk[NN],siz[NN],dep[NN],top[NN],son[NN],fa[NN],cnt; 18 int dis[NN],stk[NN],sum[NN],tp,bz[NN][25],lca,s,t,res; 19 struct SNOW{int to,val,next;}e[NN<<1]; int head[NN],rp; 20 inline void add(int x,int y,int z){ 21 e[++rp]=(SNOW){y,z,head[x]}; head[x]=rp; 22 e[++rp]=(SNOW){x,z,head[y]}; head[y]=rp; 23 } 24 inline void dfs1(int f,int x){ 25 fa[x]=f; dep[x]=dep[f]+1; siz[x]=1; 26 for(int i=head[x];i;i=e[i].next){ 27 int y=e[i].to; if(f==y) continue; 28 dis[y]=dis[x]+e[i].val; dfs1(x,y); siz[x]+=siz[y]; 29 if(siz[son[x]]<siz[y]) son[x]=y; 30 } 31 } 32 inline void dfs2(int x,int t){ 33 top[x]=t; dfn[x]=++cnt; rk[cnt]=x; 34 if(son[x]) dfs2(son[x],t); 35 for(int i=head[x];i;i=e[i].next){ 36 int y=e[i].to; 37 if(y!=fa[x]&&y!=son[x]) dfs2(y,y); 38 } 39 } 40 inline int LCA(int x,int y){ 41 while(top[x]!=top[y]){; 42 if(dep[top[x]]<dep[top[y]]) swap(x,y); 43 x=fa[top[x]]; 44 } if(dfn[x]>dfn[y]) swap(x,y); 45 return x; 46 } 47 inline void dfs(int f,int x){ 48 stk[++tp]=x; sum[tp]=dis[x]; 49 bz[x][0]=stk[upper_bound(sum+1,sum+tp+1,sum[tp]-k)-sum-1]; 50 for(int i=1;i<=20;i++) bz[x][i]=bz[bz[x][i-1]][i-1]; 51 for(int i=head[x];i;i=e[i].next) if(e[i].to!=f) dfs(x,e[i].to); 52 --tp; 53 } 54 inline int solve(int x,int y){ 55 lca=LCA(x,y); res=0; 56 for(int i=20;i>=0;i--) if(dep[lca]<=dep[bz[x][i]]) x=bz[x][i],res+=(1<<i); 57 for(int i=20;i>=0;i--) if(dep[lca]<=dep[bz[y][i]]) y=bz[y][i],res+=(1<<i); 58 if(dis[x]+dis[y]-2*dis[lca]>=k) res++; 59 return res; 60 } 61 62 namespace WSN{ 63 inline short main(){ 64 n=read(); k=read(); 65 for(int i=1,u,v,w;i<n;i++) u=read(), v=read(), w=read(), add(u,v,w); 66 dfs1(0,1); dfs2(1,1); dfs(0,1); q=read(); 67 while(q--) s=read(),t=read(),write(solve(s,t)); 68 return 0; 69 } 70 } 71 signed main(){return WSN::main();}
比较$diao$的区间$dp$，还要一个分治保证复杂度
我看的是巨佬gjy的题解，非常的清楚明白
主要其实就是等价的那一步不好想，明白那里这题就轻松解决了
1 #include<bits/stdc++.h> 2 #define int long long 3 using namespace std; 4 namespace AE86{ 5 inline int read(){ 6 int x=0,f=1;char ch=getchar(); 7 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} 8 while(ch>=‘0‘&&ch<=‘9‘){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f; 9 }inline void write(int x,char opt=‘\n‘){ 10 char ch[20];int len=0;if(x<0)x=~x+1,putchar(‘-‘); 11 do{ch[len++]=x%10+(1<<5)+(1<<4);x/=10;}while(x); 12 for(register int i=len-1;i>=0;--i)putchar(ch[i]);putchar(opt);} 13 inline int max(int a,int b){return a>b?a:b;} 14 }using namespace AE86; 15 16 const int NN=2e5+5, mod=998244353; 17 int n,a[NN],lenl,lenr,ans; 18 int fl[2][NN],fr[2][NN],dp[2][NN][2]; 19 vector<int> ll,rr; 20 21 inline void divide(int l,int r){ 22 if(l>=r) return ans=(ans+a[l])%mod,void(); int mid=(l+r)>>1; 23 divide(l,mid); divide(mid+1,r); 24 ll.clear();rr.clear(); lenl=mid-l+1; lenr=r-mid; 25 for(int i=l;i<=r;i++) dp[0][i][0]=dp[1][i][0]=dp[0][i][1]=dp[1][i][1]=0; 26 dp[1][mid][1]=a[mid]; fl[1][mid]=a[mid]; ll.push_back(fl[1][mid]); 27 for(int i=mid-1;i>=l;i--){ 28 dp[0][i][0]=max(dp[0][i+1][1],dp[0][i+1][0]); 29 dp[0][i][1]=dp[0][i+1][0]+a[i]; 30 dp[1][i][0]=max(dp[1][i+1][1],dp[1][i+1][0]); 31 dp[1][i][1]=dp[1][i+1][0]+a[i]; 32 fl[0][i]=max(dp[0][i][1],dp[0][i][0]); 33 fl[1][i]=max(dp[1][i][1],dp[1][i][0]); 34 ll.push_back(max(fl[1][i]-fl[0][i],0)); 35 } 36 dp[1][mid+1][1]=a[mid+1]; fr[1][mid+1]=a[mid+1]; rr.push_back(fr[1][mid+1]); 37 for(int i=mid+2;i<=r;i++){ 38 dp[0][i][0]=max(dp[0][i-1][1],dp[0][i-1][0]); 39 dp[0][i][1]=dp[0][i-1][0]+a[i]; 40 dp[1][i][0]=max(dp[1][i-1][1],dp[1][i-1][0]); 41 dp[1][i][1]=dp[1][i-1][0]+a[i]; 42 fr[0][i]=max(dp[0][i][1],dp[0][i][0]); 43 fr[1][i]=max(dp[1][i][1],dp[1][i][0]); 44 rr.push_back(max(fr[1][i]-fr[0][i],0)); 45 } 46 sort(ll.begin(),ll.end()); sort(rr.begin(),rr.end()); 47 for(int i=l;i<=mid;i++) ans=(ans+fl[0][i]*lenr%mod)%mod; 48 for(int i=mid+1;i<=r;i++) ans=(ans+fr[0][i]*lenl%mod)%mod; 49 int j=0,R=rr.size(),L=ll.size(); 50 for(int i=0;i<L;i++){ 51 int vl=ll[i]; 52 while(j<R && vl>=rr[j]) ++j; 53 ans=(ans+vl*j%mod)%mod; 54 } 55 j=0; 56 for(int i=0;i<R;i++){ 57 int vr=rr[i]; 58 while(j<L && vr>ll[j]) ++j; 59 ans=(ans+vr*j%mod)%mod; 60 } 61 } 62 63 namespace WSN{ 64 inline short main(){ 65 n=read(); 66 for(int i=1;i<=n;i++) a[i]=read(); 67 divide(1,n); 68 write(ans); 69 return 0; 70 } 71 } 72 signed main(){return WSN::main();}
关于正解，他死了。。。。
或者说是基于随机数据的暴力赢了。。。。
关于暴力，就是每次进行$l_i,r_i$的缩小，直到所有的都没有就结束。
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef unsigned long long ULL; 4 const int NN=5e6+5,mod=998244353; 5 int n,X,Y,ll,l[NN],r[NN]; 6 ULL A,B; 7 inline int max(int a,int b){return a>b?a:b;} 8 inline int min(int a,int b){return a<b?a:b;} 9 inline int abs(int x){return x<0?-x:x;} 10 inline void swap(int &a,int &b){a^=b^=a^=b;} 11 12 inline ULL xorshift128p(ULL &A,ULL &B){ 13 ULL T=A,S=B;A=S;T^=T<<23;T^=T>>17;T^=S^(S>>26);B=T; 14 return T+S; 15 } 16 inline void gen(int n,int ll,int X,int Y,ULL A,ULL B,int l[NN],int r[NN]){ 17 for(register int i=1;i<=n;++i){ 18 l[i]=(int)(xorshift128p(A,B)%ll+X); 19 r[i]=(int)(xorshift128p(A,B)%ll+Y); 20 if(l[i]>r[i]) swap(l[i],r[i]); 21 } 22 } 23 inline int qmo(int a,int b){ 24 int ans=1,c=mod; a%=c; 25 while(b){ 26 if(b&1) ans=(int)(1ll*ans*a%c); 27 b>>=1; a=(int)(1ll*a*a%c); 28 } 29 return ans; 30 } 31 32 int nb,mi[NN],f[NN],prel[NN],prer[NN],cnt,ans; 33 34 namespace WSN{ 35 inline short main(){ 36 cin>>n>>ll>>X>>Y; cin>>A>>B; gen(n,ll,X,Y,A,B,l,r); 37 mi[0]=nb=1; l[0]=l[n+1]=0x3fffffff; r[0]=r[n+1]=0; 38 for(register int i=1;i<=n;++i) mi[i]=(1ll*mi[i-1]*3ll%mod); 39 while(nb){ 40 ++cnt; nb=0; 41 for(register int i=1;i<=n;++i) if(l[i]<=r[i]){ 42 prel[i]=l[i]+1; prer[i]=r[i]-1; 43 prel[i]=max(prel[i],max(l[i-1],l[i+1])); 44 prer[i]=min(prer[i],min(r[i-1],r[i+1])); 45 } 46 for(register int i=1;i<=n;++i) if(l[i]<=r[i]){ 47 l[i]=prel[i]; r[i]=prer[i]; 48 l[i]>r[i] ? f[i]=cnt:nb=1; 49 } 50 } 51 for(register int i=1;i<=n;++i) 52 ans=(1ll*ans+1ll*f[i]*mi[i-1]%mod)%mod; 53 cout<<ans<<endl; 54 return 0; 55 } 56 } 57 signed main(){return WSN::main();}
然后刚开始还想着打正解，可是无法维护出正确的$RMQ$就停止了，
比较暴力的思路，考虑每一行的最大可行值代表什么，
实际上是以这一行里面的某一个$1$为中心，画出来一个正菱形，这个正菱形的 对角线/2+1。
如上这个正菱形的可行值就是$3+1=4$
那么我们可以算出每一行可行中心的横坐标范围，即
$l_i+(k-abs(i-j))<=x<=r_i-(k-abs(i-j))$，二分一个$k$，然后$check$有无一个可行的横坐标满足构成一个正菱形
可以使用$RMQ$，并且用单调队列优化$RMQ$，达到$O(n)$的神奇复杂度，本人比较弱，只会打暴力二分（严格的说进行了好多优化），如下
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef unsigned long long ULL; 4 const int NN=5e6+5,mod=998244353; 5 int n,X,Y,ll,l[NN],r[NN]; 6 ULL A,B; 7 inline int max(int a,int b){return a>b?a:b;} 8 inline int min(int a,int b){return a<b?a:b;} 9 inline int abs(int x){return x<0?-x:x;} 10 inline void swap(int &a,int &b){a^=b^=a^=b;} 11 12 inline ULL xorshift128p(ULL &A,ULL &B){ 13 ULL T=A,S=B;A=S;T^=T<<23;T^=T>>17;T^=S^(S>>26);B=T; 14 return T+S; 15 } 16 inline void gen(int n,int ll,int X,int Y,ULL A,ULL B,int l[NN],int r[NN]){ 17 for(register int i=1;i<=n;++i){ 18 l[i]=(int)(xorshift128p(A,B)%ll+X); 19 r[i]=(int)(xorshift128p(A,B)%ll+Y); 20 if(l[i]>r[i]) swap(l[i],r[i]); 21 } 22 } 23 inline int qmo(int a,int b){ 24 int ans=1,c=mod; a%=c; 25 while(b){ 26 if(b&1) ans=(int)(1ll*ans*a%c); 27 b>>=1; a=(int)(1ll*a*a%c); 28 } 29 return ans; 30 } 31 int maxn,minn,L,R,prel,prer; 32 int p1,p2,mi[NN]; 33 int ans,tmp; 34 inline bool check(int k,int now){ 35 minn=min(k,min(n-now+1,now)); 36 if(minn!=k||now-k<=0||now+k>n) return false; 37 prer=0x3fffffff; prel=-0x3fffffff; 38 for(register int i=k;i>=0;--i){ 39 p1=now-i; p2=now+i; 40 L=max(l[p1]+(k-abs(p1-now)),l[p2]+(k-abs(p2-now))); 41 R=min(r[p1]-(k-abs(p1-now)),r[p2]-(k-abs(p2-now))); 42 if(L>R) return false; 43 else if(L>prer||R<prel) return false; 44 else if(L<=prel&&prer<=R) continue; 45 else prel=max(prel,L), prer=min(prer,R); 46 } 47 return true; 48 } 49 50 namespace WSN{ 51 inline short main(){ 52 cin>>n>>ll>>X>>Y; cin>>A>>B; mi[0]=1; 53 gen(n,ll,X,Y,A,B,l,r); 54 for(register int i=1;i<=n;i++) mi[i]=(1ll*mi[i-1]*3ll%mod); 55 for(register int i=1;i<=n;++i) maxn=max(maxn,r[i]); 56 for(register int i=1;i<=n;++i){ 57 int L=0,R=min(min(maxn,n),min(n-i+1,i)),k=0; 58 while(L<=R){ 59 int mid=L+R>>1; 60 if(check(mid,i)) k=mid,L=mid+1; 61 else R=mid-1; 62 } ++k; 63 tmp=(int)(1ll*k*mi[i-1]%mod); 64 ans=(int)((1ll*ans+1ll*tmp)%mod); 65 } 66 cout<<ans<<endl; 67 return 0; 68 } 69 } 70 signed main(){return WSN::main();}
原文：https://www.cnblogs.com/hzoi-wsn/p/15252850.html
