loj2001[SDOI2017]树点染色

题意：给你一棵树，一开始每个点上的颜色互不相同。三种操作：op1：x到根的路径上的点都染上一种新的颜色。op2：设一条路径的权值为val(x,y)，求x到y路径的val。op3：询问x的子树中最大的到根路径val。n<=1e5。

标程：

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 const int mod=1e9+;

 const int N=1e6+;

 int f[N],prime[N],tot,F[N],ans,p[N],n,m,nxt,u[N],fi[N];

 int ksm(int x,int y)

 {

   int res=;

   for (;y;x=(ll)x*x%mod,y>>=)

     if (y&) res=(ll)res*x%mod;

   return res;

 }

 void pre()

 {

   f[]=f[]=fi[]=fi[]=;

   for (int i=;i<N;i++) f[i]=((ll)f[i-]+f[i-])%mod,fi[i]=ksm(f[i],mod-);

   u[]=;

   for (int i=;i<N;i++)

   {

     if (!p[i]) prime[++tot]=i,u[i]=-;//质数的u是-1！

     for (int j=;j<=tot&&(ll)prime[j]*i<N;j++)

     {

       p[prime[j]*i]=;

       if (i%prime[j]==) break;

       u[prime[j]*i]=-u[i];

     }

   }

   for (int i=;i<N;i++) F[i]=;

   for (int i=;i<N;i++)

     if (u[i]!=)

     for (int j=i;j<N;j+=i)

       F[j]=(ll)F[j]*(u[i]==?f[j/i]:fi[j/i])%mod;//注意u有可能是-1

   for (int i=;i<N;i++) F[i]=(ll)F[i]*F[i-]%mod;

 }

 int main()

 {

   pre();int T;

   scanf("%d",&T);

   while (T--)

   {

     scanf("%d%d",&n,&m);ans=;

     for (int i=;i<=min(n,m);i=nxt+)

     {

       nxt=min(n/(n/i),m/(m/i));

       ans=(ll)ans*ksm((ll)F[nxt]*ksm(F[i-],mod-)%mod,(ll)(n/i)*(m/i)%(mod-))%mod;

     }

     printf("%d\n",ans);

   }

   return ;

 }

要把lct上和原树上的father区分开啊！

题解：lct+dfs序线段树

op1一看就是lct维护access。将A颜色splay连到B颜色splay上时，A颜色splay上深度最小点（原树上的根）的子树val都-1，B颜色断开的右子树（即不在改色链上的那段）val都+1。

op2 设val[x]表示x到根的路径权值。相当于要求val[x]+val[y]-2*val[lca(x,y)]+1。线段树单点求值，注意要用dfs序查。

op3 询问子树最大值val，线段树区间Max。

时间复杂度O(nlog^2(n))。

巴特西

loj2001[SDOI2017]树点染色

最新文章

热门文章