点分治水题

CF1260F Colored Tree

一颗有 n 个节点的树，每个节点 v 有颜色 cvc_vcv，这个染色方案的权值为 ∑u,v∈[1,n],v>u,cv=cudis⁡(u,v)\sum\limits_{u,v\in[1,n],v>u,c_v=c_u}\operatorname{dis}{(u,v)}u,v∈[1,n],v>u,cv=cu∑dis(u,v)。

现在知道每个节点 v 可以染成 [lv,rv][l_v,r_v][lv,rv] 中任意颜色，求所有染色方案的权值之和。

n≤105n\le 10^5n≤105，时限 2.5 秒。

一个显然的想法是考虑每一条路径的贡献，于是自然的想到点分治。考虑过分治中心一条路径的贡献（为方便起见，后文都算的是权值期望）。

显然贡献为：

(du+dv)∣[lu,ru]∩[lv,rv]∣∣[lu,ru]∣⋅∣[lv,rv]∣(d_u+d_v)\frac{|[l_u,r_u]\cap[l_v,r_v]|}{|[l_u,r_u]|\cdot|[l_v,r_v]|}(du+dv)∣[lu,ru]∣⋅∣[lv,rv]∣∣[lu,ru]∩[lv,rv]∣

我们可以维护一个线段树，在搜到 u 的时，把 [lu,ru][l_u,r_u][lu,ru] 区间加 du∣[lu,ru]∣\frac{d_u}{|[l_u,r_u]|}∣[lu,ru]∣du。搜到 v 时，把 [lv,rv][l_v,r_v][lv,rv] 区间的和，乘以 1∣[lv,rv]∣\frac1{|[l_v,r_v]|}∣[lv,rv]∣1，加到答案里即可，这样我们就解决了上式中第一项。

对于第二项，可以反着做一遍，也可以再开一个另外含义的线段树，怎么搞都行。

复杂度 O(nlog⁡2n)\mathcal{O}(n\log^2 n)O(nlog2n)。

题解提供了一个不用点分治的做法，复杂度一样，在此先不说，因为我没读懂。

const ll INF=1e18,P=1e9+7;

inline ll mod(ll x){
    if(x>=P)return x-P;
    if(x<0)return x+P;
    return x;
}
inline ll qpow(ll x,ll y){ll res=1;while(y){if(y&1)res=res*x%P;x=x*x%P;y>>=1;}return res;}

const ll MXN=1e5+5,MNMEM=5e4;

ll n,ans,all=1,arr[MXN],lh[MXN],rh[MXN];
struct tarr{
    ll d[MXN],di[MXN];
    inline void suf(ll x,ll y){
        ll yi=y*x%P;
        for(;x<MXN;x+=x&(-x)){
            d[x]=mod(d[x]+y);
            di[x]=mod(di[x]+yi);
        }
    }
    inline ll pre(ll l){
        ll s=0,si=0;
        for(ll x=l;x;x^=x&(-x)){
            s=mod(s+d[x]);
            si=mod(si+di[x]);
        }
        return (s*(l+1)-si)%P;
    }
    inline void clr(ll x){for(;x<MXN;x+=x&(-x))d[x]=di[x]=0;}
    inline void mem(){
        memset(d,0,sizeof(d));
        memset(di,0,sizeof(di));
    }
}c,v;

vector<ll> t[MXN];
ll sz[MXN];bool vis[MXN];
inline void dfssz(ll p,ll fa){
    sz[p]=1;
    for(ll &nx:t[p])
        if(!vis[nx] && nx!=fa){
            dfssz(nx,p);
            sz[p]+=sz[nx];
        }
}
inline ll dfsrt(ll p,ll fa,ll tot){
    bool f=(sz[p]<<1)>=tot;
    for(ll &nx:t[p])
        if(!vis[nx] && nx!=fa){
            ll tmp=dfsrt(nx,p,tot);
            if(tmp)return tmp;
            f&=(sz[nx]<<1)<=tot;
        }
    return f?p:0;
}
inline void dfsm(ll p,ll fa,ll dpth){
    if(dpth<0){
        c.clr(lh[p]),c.clr(rh[p]+1);
        v.clr(lh[p]),v.clr(rh[p]+1);
    }
    else{
        ll tmp=dpth*arr[p]%P;
        c.suf(lh[p],arr[p]),c.suf(rh[p]+1,-arr[p]);
        v.suf(lh[p],tmp),v.suf(rh[p]+1,-tmp);
    }
    for(ll &nx:t[p])
        if(!vis[nx] && nx!=fa)
            dfsm(nx,p,dpth+1);
}
inline void dfsq(ll p,ll fa,ll dpth){
    ans=(ans+(dpth*(c.pre(rh[p])-c.pre(lh[p]-1))+v.pre(rh[p])-v.pre(lh[p]-1))%P*arr[p])%P;
    for(ll &nx:t[p])
        if(!vis[nx] && nx!=fa)
            dfsq(nx,p,dpth+1);
}

inline void dfz(ll p){
    dfssz(p,0);
    ll tsz=sz[p];
    vis[p=dfsrt(p,0,tsz)]=1;

    c.suf(lh[p],arr[p]),c.suf(rh[p]+1,-arr[p]);
    for(ll &nx:t[p])
        if(!vis[nx]){
            dfsq(nx,0,1);
            dfsm(nx,0,1);
        }
    if(tsz>MNMEM)c.mem(),v.mem();
    else dfsm(p,0,-INF);
    for(ll &nx:t[p])
        if(!vis[nx])
            dfz(nx);
}

int main(){
    scanf("%lld",&n);
    for(int i=1;i<=n;i++){
        scanf("%lld%lld",lh+i,rh+i);
        arr[i]=qpow(rh[i]-lh[i]+1,P-2);
        all=all*(rh[i]-lh[i]+1)%P;
    }
    for(ll i=1,ts,tt;i<n;i++){
        scanf("%lld%lld",&ts,&tt);
        t[ts].pb(tt);
        t[tt].pb(ts);
    }
    dfz(1);

    printf("%lld\n",all*(ans+P)%P);
    return 0;
}

实在找不到啥点分治好题了，只能用点分治硬做这题。

树上每个点有颜色，定义 s⁡(i,j)\operatorname{s}{(i,j)}s(i,j) 为 i 到 j 路径颜色数，对于 i∈[1,n]i\in[1,n]i∈[1,n] 求 ansi=∑j∈[1,n]s⁡(i,j)ans_i=\sum\limits_{j\in[1,n]}\operatorname{s}{(i,j)}ansi=j∈[1,n]∑s(i,j)。

n≤105n\le10^5n≤105，时限 1 秒。

这题怎么做都行，有好多线性的做法，但是我们要有拿下最劣解的追求，为了实现这一目标，考虑淀粉质的做法。

上图中，蓝色大三角表示所有搜过的子树，v 是正在查询的点，对于所有过分治中心 rt 的路径 u∼vu \sim vu∼v，考虑红色对哪些路径有贡献，发现有两种情况：

u 在某个红色节点的子树中
v∼rtv \sim rtv∼rt 上有红色节点

定义 hasc 表示（蓝色子树中）到 rt 的路径上有红色的点数，当我修改节点 u 的时候，如果发现路径 rt∼urt\sim urt∼u 上没有红色的话，我就 hasc←hasc+u 子树大小hasc\gets hasc + \text{u 子树大小}hasc←hasc+u 子树大小。

在查询时,一开始的答案为 hasc ，dfs 的过程中，如果第一次碰到一个红色点（这个点的祖先上没有红色点），那么对于其子树，红色的贡献就增加了蓝色区域的点数，回溯的时候再撤销即可。

因为每个点只有一个颜色，所以其实上述的过程是可以在 dfs 中对每个颜色同时进行的。

复杂度 O(nlog⁡n)O(n\log n)O(nlogn)。

有不少细节，尤其是在分治中心的处理上，不建议实现。

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const ll MXN = 1e5 + 5;
ll n, c[MXN];
vector<ll> g[MXN];

bool vis[MXN];
ll sz[MXN];
void dfssz(ll p, ll fa) {
    sz[p] = 1;
    for (ll nx : g[p])
        if (!vis[nx] && nx != fa) {
            dfssz(nx, p);
            sz[p] += sz[nx];
        }
}
ll dfsrt(ll p, ll fa, ll tot) {
    bool f = (sz[p] << 1) >= tot;
    for (ll nx : g[p])
        if (!vis[nx] && nx != fa) {
            ll nxr = dfsrt(nx, p, tot);
            if (nxr) return nxr;
            f &= (sz[nx] << 1) <= tot;
        }
    return f ? p : 0;
}

ll instk[MXN], ans[MXN];
//到根路径上有这个颜色的节点数
ll hasc[MXN], curans;
void dfsm(ll p, ll fa, ll tp) {
    if (!instk[c[p]]++) {
        hasc[c[p]] += tp * sz[p];
        curans += tp * sz[p];
    }
    for (ll nx : g[p])
        if (!vis[nx] && nx != fa) dfsm(nx, p, tp);
    --instk[c[p]];
}
void dfsq(ll p, ll fa, ll outofsubt) {
    if (!instk[c[p]]++) curans += outofsubt - hasc[c[p]];
    ans[p] += curans;
    for (ll nx : g[p])
        if (!vis[nx] && nx != fa) dfsq(nx, p, outofsubt);
    if (!--instk[c[p]]) curans -= outofsubt - hasc[c[p]];
}
void dfz(ll p) {
    dfssz(p, 0);
    p = dfsrt(p, 0, sz[p]);
    vis[p] = 1;
    dfssz(p, 0);

    instk[c[p]] = 1;
    for (ll nx : g[p])
        if (!vis[nx]) dfsm(nx, p, 1);
    //到根
    ans[p] += curans + sz[p];
    for (ll nx : g[p])
        if (!vis[nx]) {
            dfsm(nx, p, -1);
            curans += sz[p] - sz[nx];
            dfsq(nx, p, sz[p] - sz[nx]);
            curans -= sz[p] - sz[nx];
            dfsm(nx, p, 1);
        }
    for (ll nx : g[p])
        if (!vis[nx]) dfsm(nx, p, -1);
    instk[c[p]] = 0;
    for (ll nx : g[p])
        if (!vis[nx]) dfz(nx);
}
int main() {
    scanf("%lld", &n);
    for (ll i = 1; i <= n; i++) scanf("%lld", c + i);
    for (ll i = 1; i < n; i++) {
        ll u, v;
        scanf("%lld%lld", &u, &v);
        g[v].push_back(u);
        g[u].push_back(v);
    }
    dfz(1);
    for (ll i = 1; i <= n; i++) printf("%lld\n", ans[i]);
    return 0;
}

P3060 [USACO12NOV]Balanced Trees G

给出一棵树，每个节点上有一个括号，对于所有括号匹配的路径，求其嵌套层数最大值。

括号匹配比较有用的性质就是把 { 看成 1，} 看成 -1，最终序列的前缀和 preipre_iprei都大于等于 0，并且总和 s 为 0.

而最大嵌套层数则等于前缀和的最大值。

考虑把两个括号序列合起来：

str=str1+str2s=s1+s2max⁡(prei)=max⁡(max⁡(pre1i),s1+max⁡(pre2i))min⁡(prei)=min⁡(min⁡(pre1i),s1+min⁡(pre2i))\begin{aligned} str&=str1 + str2\cr s&=s1+s2\cr \max{(pre_i)}&=\max{(\max{(pre1_i)},s1+\max{(pre2_i)})}\cr \min{(pre_i)}&=\min{(\min{(pre1_i)},s1+\min{(pre2_i)})} \end{aligned}strsmax(prei)min(prei)=str1+str2=s1+s2=max(max(pre1i),s1+max(pre2i))=min(min(pre1i),s1+min(pre2i))

所以只需在第一次 dfs 时，判断如果前半段 pre 的最小值大于等于 0，就把前半段 pre 的最大值打到一个桶里 s1 的位置，查询就随便搞搞即可。

没时间实现了，我妈催我睡觉😡。

作者：@ethan-enhe
本文为作者原创，转载请注明出处：本文链接

阅读量 8

Previous
浅谈容斥

来发评论吧~

CF1260F Colored Tree

P3060 [USACO12NOV]Balanced Trees G

Recommend

Sushiswap前CTO撰文反思：我的领导为什么会走向失败？

关于元宇宙，你需要了解的21个真相

加密监管二三事：香港、新加坡、巴哈马

Ubisoft's next Splinter Cell game will be a "stealthier version" of As...

FBEC2021 | 影创科技 CEO 孙立：Turn-Key 时代是整个行业快速爆发的关键

诺亦腾联合创始人戴若犁：元宇宙是数字化的终局，但它绝不会一蹴而就丨钛媒体T-EDGE

FBEC2021 | 瑞欧威尔联合创始人兼 CEO 李波博士：“工业元宇宙”是为了更好赋能实体经济

I don't consider this unexpected. But I am a bit surprised by the 4-0 vote.

The tried and true method of tech journalism: hanging out at the airport, bars,...

Upcoming iOS update adds a detailed repair history to Settings | TechSpot

About Joyk