前言
T1
#include<cstdio> #define L tr[k].lc #define R tr[k].rc using namespace std; int const N=1e5+5; int n,q; int head[N],Next[N<<1],to[N<<1],t; int w[N]; int Log[N],dep[N],f[N][19],tot; int dfn[N],id[N]; struct node{ int lc,rc,maxx; }tr[N*50]; int root[N],ct; inline int read(){ int ss(0);char bb(getchar()); while(bb<48||bb>57)bb=getchar(); while(bb>=48&&bb<=57)ss=(ss<<1)+(ss<<3)+(bb^48),bb=getchar(); return ss; } inline int max(int x,int y){ return x>y?x:y; } inline void add(int x,int y){ to[++t]=y; Next[t]=head[x],head[x]=t; return ; } int ask(int l,int r,int x,int k){ if(!k)return 0; if(l>=x)return tr[k].maxx; int mid=l+r>>1; return x<=mid?max(ask(l,mid,x,L),ask(mid+1,r,x,R)):ask(mid+1,r,x,R); } inline int insert(int l,int r,int x,int y,int p){ int k=++ct,cnow=k,mid; tr[k].maxx=max(y,tr[p].maxx); do{ mid=l+r>>1; if(x<=mid)r=mid,R=tr[p].rc,p=tr[p].lc,k=L=++ct; else l=mid+1,L=tr[p].lc,p=tr[p].rc,k=R=++ct; tr[k].maxx=max(y,tr[p].maxx); }while(l^r); return cnow; } void dfs(int x,int y){ id[dfn[x]=++tot]=x; dep[tot]=dep[f[tot][0]=ask(1,N,w[x]+1,root[y])]+1; for(register int i=0,lt=Log[dep[tot]];i<lt;++i) f[tot][i+1]=f[f[tot][i]][i]; root[x]=insert(1,N,w[x],tot,root[y]); for(int i=head[x];i;i=Next[i]) if(to[i]^y)dfs(to[i],x); return ; } int main(){ //freopen("2.in","r",stdin); //freopen("1.out","w",stdout); n=read(),q=read(); Log[0]=-1; for(register int i=1;i<=n;++i)w[i]=read(),Log[i]=Log[i>>1]+1; for(register int i=1,ff,tt;i<n;++i) ff=read(),tt=read(),add(ff,tt),add(tt,ff); dfs(1,0); while(q--){ int x=read(),y=dfn[read()],gl=ask(1,N,read()+1,root[x]); if(gl<y){puts("0");continue;} int ans=1; for(register int i=Log[dep[gl]];~i;--i) if(f[gl][i]>=y)ans+=1<<i,gl=f[gl][i]; printf("%d\n",ans); } return 0; }
T2
#include<cstdio> #define ll long long using namespace std; int const N=1e5+5,M=1e6+5,mod=1e9+7; int n,e,du[N],w[N]; inline int read(){ int ss(0);char bb(getchar()); while(bb<48||bb>57)bb=getchar(); while(bb>=48&&bb<=57)ss=(ss<<1)+(ss<<3)+(bb^48),bb=getchar(); return ss; } inline ll power(ll x,int y){ ll as=1; for(;y;y>>=1,x=x*x%mod) if(y&1)as=as*x%mod; return as; } int main(){ //freopen("1.in","r",stdin); //freopen("1.out","w",stdout); n=read(),e=read(); for(register int i=1;i<=n;++i)w[i]=n-1; for(register int i=1,ff,tt;i<=e;++i)++du[read()],--w[read()]; long long ans=1ll*n*(n-1)*(n-2)/2/3; long long inv2=power(2,mod-2),inv4=power(4,mod-2); for(register int x=1;x<=n;++x){ ans-=(1ll*du[x]*(du[x]-1)>>1)+(1ll*du[x]*(w[x]-du[x])*inv2) +(1ll*(w[x]-du[x])*(w[x]-du[x]-1)>>1)*inv4; ans=(ans%mod+mod)%mod; } printf("%lld",ans); return 0; }
T3
#include<cstdio> #define ll long long using namespace std; int const N=1e5+5,M=2e7+1,mod=1e9+7; int n,tot; int a[N],b[N],mx[N]; ll ans; int t[M<<1],fac[M],inv[M]; inline int read(){ int ss(0),pp(1);char bb(getchar()); for(;bb<48||bb>57;bb=getchar())if(bb==‘-‘)pp=-1; while(bb>=48&&bb<=57)ss=(ss<<1)+(ss<<3)+(bb^48),bb=getchar(); return ss*pp; } inline int max(int x,int y){ return x>y?x:y; } inline ll power(ll x,int y){ ll as=1; for(;y;y>>=1,x=x*x%mod) if(y&1)as=as*x%mod; return as; } inline ll C(int x,int y){//printf("%d %d\n",x,y); return x<y?0:1ll*fac[x]*inv[y]%mod*inv[x-y]%mod; } inline int down(int x){ return x<mod?x:x-mod; } int main(){ //freopen("2.in","r",stdin); //freopen("1.out","w",stdout); n=read(); for(register int i=1;i<=n;++i) b[i]=(a[i]=read())+read(),tot+=b[i]; for(register int i=n;i;--i)mx[i]=max(a[i],mx[i+1]); fac[0]=fac[1]=1; for(register int i=2;i<=tot;++i)fac[i]=1ll*fac[i-1]*i%mod; inv[tot]=power(fac[tot],mod-2); for(register int i=tot;i;--i)inv[i-1]=1ll*inv[i]*i%mod; for(register int i=1;i<=n;++i){ for(register int j=-a[i],z=b[i],lt=z-a[i];j<=lt;++j) ans=(ans+C(z,j+a[i])*t[j+M])%mod; for(register int j=max(-mx[i+1],a[i]-b[i]);j<=a[i];++j) t[j+M]=down(t[j+M]+C(b[i],a[i]-j)); } printf("%lld",(ans<<1)%mod); return 0; }
原文：https://www.cnblogs.com/remarkable/p/11711327.html
