分治算法综合（三）

这篇博文概括一下之前的点分治
此外阐述了树分治中的点分治，边分治
以及动态树分治

$\textbf{CDQ}$分治也做了概括

点分治总结

$\textbf{algorithm1}$

• 找到树的重心 $\text{root}$ 作为初始根节点
  $\textbf{solve}(x\leftarrow root, ans)$
  特别说明，这里只需要在 $\textbf{solve}(x, ans)$ 中使用 $vis[\cdots]$ 标记防止栈溢出
  为了防止其余操作在递归时候栈溢出，避免出现自环
  将父节点 $pa$ 也作为参数传递，进入递归
  $\textbf{getDep}(x, pa), \textbf{getRoot}(x, pa)$
  $\textbf{if} \ (y \in son(x))=pa \ \textbf{or} \ vis[y], \textbf{break}$

• $cal(x)$ 统计点对的个数， $ans = \sum cal(x)$

  • 在 $cal(x)$ 的时候， 得到每个点的 $dep[\cdots] \rightarrow vec[\cdots ]$
    并且将其缓存起来， 这一步可以通过执行 $\text{getDep}()$ 完成
  • 根据 $vec[\cdots]$, 做相关的统计

• 点分治，删除根节点， 将子树 $y$ 看成无根树，递归执行
  $\textbf{for} \ \forall y \in son(x)$

  • 减掉 $y$ 作为孩子节点的统计结果
    此时 $y$ 要作为无根树来统计， 要让 $ans -=cal(y)$
    而 $y$ 作为孩子节点，记得 $dep_y = dep_x + w(x, y)$
    之后再 $ans -= cal(y)$

  • 重新求子树 $y$ 作为无根树时候的树的重心
    $sn= size_y$, 总节点数不再是 $n$ 个了

$\textbf{algorithm2}$
区别就在于 $\textbf{cal}()$ 用树状数组统计
$\textbf{cal}(x, ans), x\leftarrow root$

• 将 $dep_x \rightarrow \text{fwick}[\cdots]$
  $\text{fwick}.add(dep_x, 1)$

• $\textbf{for} \ \forall y \in son(x)$

  • 对每一个子树 $y$ 建立一个 $\text{vec}[\cdots]$, 存储子树节点的 $\text{dep}[\cdots]$
    $\textbf{getDep}(y, x) \rightarrow \text{vec}[\cdots]$
    此时不要将 $\text{vec}[\cdots]$ 的元素加入树状数组
    这个保证了 $K-vec[\cdots]$ 一定是属于其他子树的点 $\textbf{or}$ 根节点
    $ans = \sum \text{fwick}.ask(K-vec[\cdots])$

  • 更新完 $ans$ 之后再将 $vec[\cdots]$ 放入树状数组中
    $\text{fwick}.add(vec[\cdots], 1)$
    此外，维护一个队列 $\text{que}$，统计完 $\text{ans}$ 之后
    对树状数组进行还原

Luogu2634

这里也是做一个树上统计
$cnt = [0, 1, 2 \bmod (3)]$
统计路径和 $\text{sum}$, $cnt[sum \bmod 3]++$

$$cal() = C_{cnt[1]}^1 \cdot C_{cnt[2]}^1 \cdot2 + C_{cnt[0]}^1 \cdot C_{cnt[0]} ^1$$

套用 $\textbf{algorithm1}$ 的模版，只不过多一步 $\text{cal()}$

const int maxn = 1e5 + 10;
const int inf = 0x3f3f3f3f;
const int mod = 3;
int n;

inline ll gcd(ll a, ll b) {
    return b == 0 ? a : gcd(b, a % b);
}

class Edge {
public:
    int to, w;
    Edge* next;
    Edge() {}
    Edge(int to, int w) : to(to), w(w) {
        next = NULL;
    }
} edges[maxn << 1], *head[maxn];

int M = 0;

void initG() {
    M = 0;
    memset(head, 0, sizeof(head));
}

void add(int u, int v, int w) {
    edges[++M] = Edge(v, w);
    edges[M].next = head[u];
    head[u] = &edges[M];
}

// == gravity ==
int root = 0;
int sz[maxn];
int vis[maxn];
int sn = n;

void getRoot(int x, int pa, int& res) {
    sz[x] = 1;
    int maxpart = 0;
    for(const Edge* e = head[x]; e; e = e->next) {
        int y = e->to;
        if(vis[y] || y == pa) continue;
        getRoot(y, x, res);

        sz[x] += sz[y];
        maxpart = max(maxpart, sz[y]);
    }
    maxpart = max(maxpart, sn - sz[x]);

    if(maxpart < res) {
        res = maxpart;
        root = x;
    }
}
// == gravity finished ==

ll cnt[mod + 3];

void dfs(int x, int pa, int dep) {
    ++cnt[dep % mod];
    for(const Edge* e = head[x]; e; e = e->next) {
        int y = e->to;
        int w = e->w;

        if(vis[y] || y == pa) continue;
        int dep2 = (dep + w) % mod;
        dfs(y, x, dep2);
    }
}


inline ll cal(int x, int dep) {
    memset(cnt, 0, sizeof(cnt));
    dfs(x, 0, dep);

    ll ans = 1ll * cnt[0] * cnt[0] + 1ll * 2 * cnt[1] * cnt[2];
    return ans;
}



// == work ==
void work(int x, ll& ans) {
    vis[x] = 1;
    ans += cal(x, 0);

    for(const Edge* e = head[x]; e; e = e->next) {
        int y = e->to;
        int w = e->w;

        if(vis[y]) continue;

        ans -= cal(y, w);

        int res = inf;
        sn = sz[y];
        root = 0;
        getRoot(y, 0, res);

        work(root, ans);
    }
}
// == work finished ==

void init() {
    memset(sz, 0, sizeof(sz));
    memset(vis, 0, sizeof(vis));
    sn = n;

    memset(cnt, 0, sizeof(cnt));
}


int main() {
    freopen("input.txt", "r", stdin);
    scanf("%d", &n);
    init();
    initG();

    _for(i, 0, n - 1) {
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        add(x, y, z % mod);
        add(y, x, z % mod);
    }

    // then solve
    int res = inf;
    getRoot(1, 0, res);

    ll ans = 0;
    work(root, ans);

    ll p = n * n;
    ll g = gcd(ans, p);

    ans /= g, p /= g;
    printf("%lld/%lld\n", ans, p);
}

点分治计数问题

计数问题一般使用 $\textbf{algorithm2}$

Luogu3806

const int maxn = 1e5 + 10;
const int Maxn = 1e7 + 3;
const int inf = 0x3f3f3f3f;
int n, m;

int ans[maxn];
int qry[maxn];

class Edge {
public:
    int to, w;
    Edge* next;
    Edge() {}
    Edge(int to, int w) : to(to), w(w) {}
} edges[maxn << 1], *head[maxn];

int M = 0;
int K;

void initG() {
    M = 0;
    memset(head, 0, sizeof(head));
}

void add(int u, int v, int w) {
    edges[++M] = Edge(v, w);
    edges[M].next = head[u];
    head[u] = &edges[M];
}

int root = 0;
int sz[maxn];
int vis[maxn];
int sn = n;

void getRoot(int x, int pa, int& res) {
    sz[x] = 1;
    int maxpart = 0;
    for(const Edge* e = head[x]; e; e = e->next) {
        int y = e->to;
        int w = e->w;

        if(vis[y] || y == pa) continue;

        getRoot(y, x, res);
        sz[x] += sz[y];

        maxpart = max(maxpart, sz[y]);
    }
    maxpart = max(maxpart, sn - sz[x]);
    if(maxpart < res) {
        res = maxpart;
        root = x;
    }
}

int dep[maxn];
int C[Maxn << 1];

void dfs(int x, int pa, vector<int>& vec) {
    vec.push_back(dep[x]);
    for(const Edge* e = head[x]; e; e = e->next) {
        int y = e->to;
        int w = e->w;

        if(vis[y] || y == pa) continue;
        dep[y] = dep[x] + w;
        dfs(y, x, vec);
    }
}

queue<int> buf;
inline void cal(int x) {
    assert(dep[x] == 0);
    C[dep[x]] = 1;
    for(const Edge* e = head[x]; e; e = e->next) {
        int y = e->to;
        int w = e->w;

        if(vis[y]) continue;
        dep[y] = dep[x] + w;
        vector<int> vec;
        dfs(y, x, vec);

        for(auto v : vec) _rep(k, 1, m) {
            //debug(v);
            if(qry[k] >= v) ans[k] |= C[qry[k] - v];
        }
        for(auto v : vec) {
            buf.push(v);
            C[v] = 1;
        }
    }
    while (buf.size()) {
        int x = buf.front();
        buf.pop();

        C[x] = 0;
    }
    C[dep[x]] = 0;
}

void solve(int x) {
    vis[x] = 1;
    dep[x] = 0;

    cal(x);

    for(const Edge *e = head[x]; e; e = e->next) {
        int y = e->to;
        int w = e->w;

        if(vis[y]) continue;

        sn = sz[y];
        root = 0;
        int res = inf;
        getRoot(y, 0, res);

        solve(root);
    }
}


void init() {
    memset(sz, 0, sizeof(sz));
    memset(vis, 0, sizeof(vis));
    sn = n;
    memset(dep, 0, sizeof(dep));
    memset(ans, 0, sizeof(ans));
    memset(C, 0, sizeof(C));
}


int main() {
    freopen("input.txt", "r", stdin);
    scanf("%d%d", &n, &m);
    init();
    initG();

    _for(i, 1, n) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        add(u, v, w);
        add(v, u, w);
    }

    _rep(k, 1, m) scanf("%d", &qry[k]);

    // then solve
    int res = inf;
    getRoot(1, 0, res);
    solve(root);


    _rep(k, 1, m) {
        if(ans[k]) printf("AYE\n");
        else printf("NAY\n");
    }

}

点分树和计数问题

Luogu2664

注意，第二次 $\textbf{calculate2()}$ 之前的一大堆操作
$sum -= size_y, num[color_x]-=size_y$
是为了去重
否则的话，在第二次 $\textbf{calculate2()}$ 的时候
$ans[x] += (\sum)+tot2\cdot (sz[x]-sz[y])$
不去重的话，会导致 $(x\rightarrow y)$ 及其子树重复计数统计

// ============================================================== //

const int maxn = 1e5 + 10;
const int inf = 0x3f3f3f3f;
int n;
int M = 0;
int color[maxn];

class Edge {
public:
    int to, w;
    Edge *next;
    Edge() {}
    Edge(int to, int w) : to(to), w(w) {
        next = NULL;
    }
} edges[maxn << 1], *head[maxn];

void initG() {
    M = 0;
    memset(head, 0, sizeof(head));
}

void add(int u, int v, int w) {
    edges[++M] = Edge(v, w);
    edges[M].next = head[u];
    head[u] = &edges[M];
}

int sn = n;
int sz[maxn];
int root = 0;
int vis[maxn];
ll ans[maxn];

void getRoot(int x, int pa, int &res) {
    sz[x] = 1;
    int maxpart = 0;
    for(const Edge* e = head[x]; e; e = e->next) {
        int y = e->to;
        int w = e->w;
        if(vis[y] || y == pa) continue;

        getRoot(y, x, res);
        sz[x] += sz[y];
        maxpart = max(maxpart, sz[y]);
    }
    maxpart = max(maxpart, sn - sz[x]);
    if(maxpart < res) {
        res = maxpart;
        root = x;
    }
}

ll num[maxn], cnt[maxn];

void clear(int x, int pa) {
    cnt[color[x]] = num[color[x]] = 0;
    sz[x] = 1;

    for(const Edge *e = head[x]; e; e = e->next) {
        int y = e->to;
        int w = e->w;

        if(vis[y] || y == pa) continue;

        clear(y, x);
        sz[x] += sz[y];
    }
}

void calculate1(int x, int pa, ll& sum) {
    if(++cnt[color[x]] == 1) {
        sum += sz[x];
        num[color[x]] += sz[x];
    }

    for(const Edge *e = head[x]; e; e = e->next) {
        int y = e->to;
        int w = e->w;
        if(y == pa || vis[y]) continue;

        calculate1(y, x, sum);
    }

    --cnt[color[x]];
}

void change(int x, int pa, int sgn, ll& sum) {
    if(++cnt[color[x]] == 1) {
        sum += sgn * sz[x];
        num[color[x]] += sgn * sz[x];
    }

    for(const Edge *e = head[x]; e; e = e->next) {
        int y = e->to;
        int w = e->w;

        if(y == pa || vis[y]) continue;

        change(y, x, sgn, sum);
    }
    --cnt[color[x]];
}

void calculate2(int x, int pa, int cnt2, int other, ll& sum) {
    if(++cnt[color[x]] == 1) {
        cnt2++;
        sum -= num[color[x]];
    }

    ans[x] += sum + 1ll * other * cnt2;

    for(const Edge *e = head[x]; e; e = e->next) {
        int y = e->to;
        int w = e->w;

        if(vis[y] || y == pa) continue;
        calculate2(y, x, cnt2, other, sum);
    }

    if(--cnt[color[x]] == 0) {
        cnt2--;
        sum += num[color[x]];
    }
}

void work(int x, ll& sum) {
    vis[x] = 1;
    sum = 0;
    clear(x, -1);

    calculate1(x, -1, sum);
    ans[x] += 1ll * sum;

    for(const Edge* e = head[x]; e; e = e->next) {
        int y = e->to;
        int w = e->w;
        if(vis[y]) continue;

        ++cnt[color[x]];
        change(y, x, -1, sum);
        sum -= sz[y];
        num[color[x]] -= sz[y];

        calculate2(y, x, 0, sz[x] - sz[y], sum);

        change(y, x, 1, sum);
        sum += sz[y];
        num[color[x]] += sz[y];
        --cnt[color[x]];
    }

    for(const Edge* e = head[x]; e; e = e->next) {
        int y = e->to;
        if(vis[y]) continue;

        root = -1;
        sn = sz[y];
        int res = inf;
        getRoot(y, -1, res);

        work(root, sum);
    }
}

void init() {
    sn = n;
    memset(sz, 0, sizeof(sz));
    memset(vis, 0, sizeof(vis));
    memset(ans, 0, sizeof(ans));
    memset(num, 0, sizeof(num));
    memset(cnt, 0, sizeof(cnt));
}

int main() {
    freopen("input.txt", "r", stdin);
    scanf("%d", &n);
    initG();
    init();

    _rep(i, 1, n) scanf("%d", &color[i]);
    _for(i, 1, n) {
        int x, y;
        scanf("%d%d", &x, &y);
        add(x, y, 1);
        add(y, x, 1);
    }

    // input data finished
    root = -1;
    ll sum = 0;
    int res = inf;
    getRoot(1, -1, res);

    work(root, sum);

    _rep(i, 1, n) printf("%lld\n", ans[i]);
}