CF1260F Colored Tree

送我校两名学长去女装的题。

题目

题意：给定一棵树，每个节点有一个颜色 \(h_i\)，\(h_i\) 为 \([L_i,R_i]\) 内的一个整数。对于所有 \(\prod(R_i-L_i+1)\) 种不同的染色方案，求出下列式子之和：\(\sum_{h_i=h_j,1\leq i<j\leq n}\operatorname{dis}(i,j)\)。
\(n\leq 10^5,1\leq L_i\leq R_i\leq 10^5\)。答案对大质数取模。

一千个人有一千零一种做法。

记 \(len_i=r_i-l_i+1,p=\prod_i len_i\)。

考虑对每种颜色算贡献。那么颜色 \(h\) 的贡献为：

\(\sum_{l_i\le h\le r_i}\sum_{l_j\le h\le r_j,j<i}dis(i,j)\frac{p}{len_ilen_j}\)

把 \({dis}(i,j)\) 拆出来：

\(\sum_{l_i\le h\le r_i}\sum_{l_j\le h\le r_j,j<i}[{dep}_i+{dep}_j-2{dep}_{{lca}(i,j)}]\frac{p}{len_ilen_j}\)

把一些东西往前挪：

\(\sum_{l_i\le h\le r_i}\frac{p}{len_i}\sum_{l_j\le h\le r_j,j<i}[{dep}_i+{dep}_j-2{dep}_{{lca}(i,j)}]\frac{1}{len_j}\)

整理一下：

\(\sum_{l_i\le h\le r_i}\frac{p}{len_i}[({dep}_i\sum_{l_j\le h\le r_j,j<i}\frac{1}{len_j})+(\sum_{l_j\le h\le r_j,j<i}\frac{{dep}_j}{len_j})-2(\sum_{l_j\le h\le r_j,j<i}\frac{{dep}_{{lca}(i,j)}}{len_j})]\)

从 \(1\) 到 \(100\ 000\) 去枚举 \(h\)，一个点的贡献自然是在 加入时（\(l\) 时刻）加上，然后在 删除时（\(r\) 时刻）减掉。

于是我们要维护右边那三坨东西。前面两个随便维护，第三个采取 这题 的方法维护即可。

使用树剖就是 \(O(n\log^2 n)\) 的，用 LCT 就是 \(O(n\log n)\)。

于是这题就做完了。

#include<bits/stdc++.h>
typedef long long ll;
const int N=1e5+3,M=1e9+7,K=18;
#define Md (L+R>>1)
struct segment_tree{
    int s[1<<K],lz[1<<K];
    inline void Down(int L,int R,int k){
        lz[k<<1]=(lz[k<<1]+lz[k])%M;
        lz[k<<1|1]=(lz[k<<1|1]+lz[k])%M;
        s[k<<1]=(s[k<<1]+(ll)lz[k]*(Md-L+1))%M;
        s[k<<1|1]=(s[k<<1|1]+(ll)lz[k]*(R-Md))%M;
        lz[k]=0;
    }
    int Sum(int l,int r,int L,int R,int k){
        if(l>r)return 0;
        if(l<=L&&R<=r)return s[k];
        Down(L,R,k);
        if(l>Md)return Sum(l,r,Md+1,R,k<<1|1);
        if(r<=Md)return Sum(l,r,L,Md,k<<1);
        return(Sum(l,r,L,Md,k<<1)+Sum(l,r,Md+1,R,k<<1|1))%M;
    }
    void Add(int l,int r,int a,int L,int R,int k){
        if(l>r)return;
        if(l<=L&&R<=r){
          lz[k]=(lz[k]+a)%M;
          s[k]=(s[k]+(ll)a*(R-L+1))%M;
          return;
        }
        Down(L,R,k);
        if(l<=Md)Add(l,r,a,L,Md,k<<1);
        if(r>Md)Add(l,r,a,Md+1,R,k<<1|1);
        s[k]=(s[k<<1]+s[k<<1|1])%M;
    }
}t;
struct edge{int v,nxt;}g[N+N];
int n,head[N],k,dep[N],prod,invl[N],inv[N],s,s0,s1,ans,dfn[N],son[N],siz[N],top[N],fa[N];
inline void Insert(int u,int v){g[++k]=(edge){v,head[u]};head[u]=k;}
struct update{
    int x,u,f;
    bool operator<(const update&b)const{return x<b.x;}
}upd[N+N];
void Dfs(int u){
    int v;
    siz[u]=1;
    for(int i=head[u];i;i=g[i].nxt)if((v=g[i].v)!=fa[u])
      dep[v]=dep[u]+1,fa[v]=u,Dfs(v),siz[u]+=siz[v],son[u]=siz[son[u]]>siz[v]?son[u]:v;
}
void Dfs1(int u){
    int v;
    dfn[u]=++k,top[u]=top[u]?top[u]:u;
    if(son[u])top[son[u]]=top[u],Dfs1(son[u]);
    for(int i=head[u];i;i=g[i].nxt)if((v=g[i].v)!=fa[u]&&v!=son[u])
      Dfs1(v);
}
inline void Pathadd(int u,int a){
    for(;u;u=fa[top[u]])
      t.Add(dfn[top[u]==1?son[1]:top[u]],dfn[u],a,1,n,1);
}
inline int Pathsum(int u){
    int s=0;
    for(;u;u=fa[top[u]])
      s=(s+t.Sum(dfn[top[u]==1?son[1]:top[u]],dfn[u],1,n,1))%M;
    return s;
}
int main(){
    int u,v,l,r,f;
    scanf("%d",&n);
    inv[1]=1;for(int i=2;i<N;i++)inv[i]=(ll)inv[M%i]*(M-M/i)%M;
    prod=1;
    for(u=1;u<=n;u++){
      scanf("%d%d",&l,&r);
      invl[u]=inv[r-l+1];
      prod=(ll)prod*(r-l+1)%M;
      upd[u]=(update){l,u,1};
      upd[u+n]=(update){r+1,u,M-1};
    }
    std::sort(upd+1,upd+1+n+n);
    for(int i=1;i<n;i++)scanf("%d%d",&u,&v),Insert(u,v),Insert(v,u);
    Dfs(1);
    k=0,Dfs1(1);
    for(int i=1,j=1;i<N;i++){
      for(;upd[j].x==i;j++){
        u=upd[j].u,f=upd[j].f;
        s0=(s0+(ll)invl[u]*f)%M;
        s1=(s1+(ll)invl[u]*dep[u]%M*f)%M;
        Pathadd(u,(ll)invl[u]*f%M);
        s=(s+(ll)f*prod%M*invl[u]%M*(((ll)dep[u]*s0+s1-2*Pathsum(u)%M+M)%M))%M;
      }
      ans=(ans+s)%M;
    }printf("%d\n",ans);
    return 0;
}

CF1260F Colored Tree

原文：https://www.cnblogs.com/Camp-Nou/p/12401297.html