标签: 点分治

[洛谷2664]树上游戏 题解

[洛谷2664]树上游戏 题解

题目地址:洛谷:【P2664】树上游戏 – 洛谷

题目描述

lrb有一棵树,树的每个节点有个颜色。给一个长度为n的颜色序列,定义s(i,j) 为i 到j 的颜色数量。以及
sum_i = \sum_{j=1}^n s(i, j)
现在他想让你求出所有的sum[i]

输入输出格式

输入格式:
第一行为一个整数n,表示树节点的数量
第二行为n个整数,分别表示n个节点的颜色c[1],c[2]……c[n]
接下来n-1行,每行为两个整数x,y,表示x和y之间有一条边

输出格式:
输出n行,第i行为sum[i]

输入输出样例

输入样例#1:

5
1 2 3 2 3
1 2
2 3
2 4
1 5

输出样例#1:

10
9
11
9
12

说明

sum[1]=s(1,1)+s(1,2)+s(1,3)+s(1,4)+s(1,5)=1+2+3+2+2=10
sum[2]=s(2,1)+s(2,2)+s(2,3)+s(2,4)+s(2,5)=2+1+2+1+3=9
sum[3]=s(3,1)+s(3,2)+s(3,3)+s(3,4)+s(3,5)=3+2+1+2+3=11
sum[4]=s(4,1)+s(4,2)+s(4,3)+s(4,4)+s(4,5)=2+1+2+1+3=9
sum[5]=s(5,1)+s(5,2)+s(5,3)+s(5,4)+s(5,5)=2+3+3+3+1=12
对于40%的数据,n<=2000
对于100%的数据,1<=n,c[i]<=10^5

题解

参考资料:题解 P2664 【树上游戏】 – Salamander 的博客 – 洛谷博客
超麻烦的点分治,说实话我在写这篇博文的时候自己都不是很懂。
对于每一个重心,我们先计算其子树内点对它答案的贡献,该贡献即为每种颜色在每条路径第一次出现的位置对应的子树大小之和。我们把子树中每种颜色在每条路径第一次出现的位置的子树大小记为cnt数组,该数组的意义实际上就是包含该种颜色的路径数,则子树内点对重心的贡献就是对cnt数组求和。
接着考虑计算经过重心的路径的贡献。对于每个单独的子树,我们可以求出类似上述cnt数组定义的ct数组。对于一个出现在重心到子树节点x的路上上的颜色col,它会与除了该子树以外的其他到重心路径上无该颜色的点组成一条没有被计算过的路径,因此该颜色会对该点的sum数组产生(siz[rt]-siz[v])-(cnt[col]-ct[col])这么多贡献,同时该颜色也会对该点的子树产生贡献,因此要把这个贡献给传递到子树中去。另外,还有可能在别的子树出现过的颜色对该点的贡献,实际上就是对cnt[col]-ct[col]求和。
总复杂度O(n \log n)

代码

// Code by KSkun, 2018/6
#include <cstdio>
#include <cctype>  
#include <cstring>

#include <algorithm>
#include <vector>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) 
        ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1;
    register char c = fgc();
    while(!isdigit(c)) {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(isdigit(c)) {
        res = (res << 1) + (res << 3) + c - '0';
        c = fgc();
    }
    return res * neg;
}

const int MAXN = 100005;

std::vector<int> gra[MAXN];

int n, c[MAXN];

int siz[MAXN], rt, rtsiz;
bool vis[MAXN];

inline void findrt(int u, int fa, int tot) {
    siz[u] = 1; int mxsiz = 0;
    for(int i = 0; i < gra[u].size(); i++) {
        int v = gra[u][i];
        if(vis[v] || v == fa) continue;
        findrt(v, u, tot);
        siz[u] += siz[v];
        mxsiz = std::max(mxsiz, siz[v]);
    }
    mxsiz = std::max(mxsiz, tot - siz[u]);
    if(mxsiz < rtsiz) {
        rt = u; rtsiz = mxsiz;
    }
}

inline void calsiz(int u, int fa) {
    siz[u] = 1;
    for(int i = 0; i < gra[u].size(); i++) {
        int v = gra[u][i];
        if(vis[v] || v == fa) continue;
        calsiz(v, u);
        siz[u] += siz[v];
    }
}

int cnt[MAXN], cct[MAXN], ct[MAXN], col[MAXN], cl[MAXN], top, tp, tot, path;
LL sum[MAXN];
int has[MAXN];
bool exist[MAXN];

inline void dfs(int u, int fa, int *cnt) {
    if(!exist[c[u]]) {
        col[++top] = c[u]; exist[c[u]] = true;
    }
    if(++has[c[u]] == 1) cnt[c[u]] += siz[u];
    for(int i = 0; i < gra[u].size(); i++) {
        int v = gra[u][i];
        if(vis[v] || v == fa) continue;
        dfs(v, u, cnt);
    }
    has[c[u]]--;
}

inline void modify(int u, int fa, LL lst) {
    LL tag = lst;
    if(++has[c[u]] == 1) tag += path - cnt[c[u]];
    sum[u] += tot + tag;
    for(int i = 0; i < gra[u].size(); i++) {
        int v = gra[u][i];
        if(vis[v] || v == fa) continue;
        modify(v, u, tag);
    }
    has[c[u]]--;
}

inline void calc(int u) {
    calsiz(u, 0);
    top = tot = 0;
    dfs(u, 0, cnt);
    for(int i = 1; i <= top; i++) {
        exist[col[i]] = false;
    }
    tp = top;
    for(int i = 1; i <= top; i++) {
        tot += cnt[cl[i] = col[i]];
        cct[col[i]] = cnt[col[i]];
    }
    sum[u] += tot;
    int temp = tot;
    for(int i = 0; i < gra[u].size(); i++) {
        int v = gra[u][i];
        if(vis[v]) continue;
        has[c[u]] = true; top = 0;
        dfs(v, u, ct);
        has[c[u]] = false;
        for(int j = 1; j <= top; j++) {
            exist[col[j]] = false;
        }
        cnt[c[u]] -= siz[v];
        tot -= siz[v];
        for(int j = 1; j <= top; j++) {
            cnt[col[j]] -= ct[col[j]];
            tot -= ct[col[j]];
        }
        path = siz[u] - siz[v];
        modify(v, u, 0);
        cnt[c[u]] += siz[v];
        tot = temp;
        for(int j = 1; j <= top; j++) {
            cnt[col[j]] = cct[col[j]];
            ct[col[j]] = 0;
        }
    }
    for(int i = 1; i <= tp; i++) {
        cnt[cl[i]] = 0;
    }
    vis[u] = true;
}

inline void divide(int u) {
    calc(u);
    for(int i = 0; i < gra[u].size(); i++) {
        int v = gra[u][i];
        if(vis[v]) continue;
        rt = 0; rtsiz = n; findrt(v, u, siz[v]);
        divide(rt);
    }
}

int main() {
    n = readint();
    for(int i = 1; i <= n; i++) {
        c[i] = readint();
    }
    for(int i = 1, u, v; i < n; i++) {
        u = readint(); v = readint();
        gra[u].push_back(v); gra[v].push_back(u);
    }
    rt = 0; rtsiz = n; findrt(1, 0, n);
    divide(rt);
    for(int i = 1; i <= n; i++) {
        printf("%lld\n", sum[i]);
    }
    return 0;
}
[SPOJ-QTREE4]Query on a tree IV 题解

[SPOJ-QTREE4]Query on a tree IV 题解

题目地址:洛谷:【SP2666】QTREE4 – Query on a tree IV – 洛谷、SPOJ:SPOJ.com – Problem QTREE4

SPOJ QTREE系列:

题目描述

You are given a tree (an acyclic undirected connected graph) with N nodes, and nodes numbered 1,2,3…,N. Each edge has an integer value assigned to it(note that the value can be negative). Each node has a color, white or black. We define dist(a, b) as the sum of the value of the edges on the path from node a to node b.
All the nodes are white initially.
We will ask you to perfrom some instructions of the following form:

  • C a : change the color of node a.(from black to white or from white to black)
  • A : ask for the maximum dist(a, b), both of node a and node b must be white(a can be equal to b). Obviously, as long as there is a white node, the result will alway be non negative.

给一棵有边权的树,最初点全是白色的,操作:1.改变一个点的颜色(黑→白,白→黑)2.询问最远两个白点间距离。

输入输出格式

输入格式:
In the first line there is an integer N (N <= 100000)
In the next N-1 lines, the i-th line describes the i-th edge: a line with three integers a b c denotes an edge between a, b of value c (-1000 <= c <= 1000)
In the next line, there is an integer Q denotes the number of instructions (Q <= 100000)
In the next Q lines, each line contains an instruction “C a” or “A”

输出格式:
For each “A” operation, write one integer representing its result. If there is no white node in the tree, you should write “They have disappeared.”.

输入输出样例

输入样例#1:

3
1 2 1
1 3 1
7
A
C 1
A
C 2
A
C 3
A

输出样例#1:

2
2
0
They have disappeared.

题解

本题可以用点分治的做法解决,做法类似[ZJOI2007]捉迷藏 题解 | KSkun’s Blog。这里介绍边分治的做法。
我们在中心边位置维护两个堆,一个表示左边子树的各个白点距离,一个表示右边子树的。单独维护每个分治结构的答案,我们可以在一个统计最大值的时候顺带把子分治结构的最大值也计算进来,这样询问的时候只需要询问根分支结构的答案即可。在加点的的过程中,记录下这个点会影响到的堆的数据。变白要把这个点放进堆里,变黑只需要打标记。而每一次更新答案的时候,从堆顶把黑点全扔掉就好。如果用数组/vector来存的话,这个更新要根据倒序,因此倒序才是分治结构从底向根的顺序。

代码

// Code by KSkun, 2018/3
#include <cstdio>
#include <cstring>

#include <vector>
#include <algorithm>
#include <queue>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1;
    register char c = fgc();
    while(c < '0' || c > '9') {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(c >= '0' && c <= '9') {
        res = res * 10 + c - '0';
        c = fgc();
    }
    return res * neg;
}

inline bool isop(char c) {
    return c == 'A' || c == 'C';
}

inline char readop() {
    char c;
    while(!isop(c = fgc()));
    return c;
}

const int MAXN = 200005, INF = 2e9;

int n, q, col[MAXN], ans;

struct Edge {
    int to, w, nxt;
} gra[MAXN << 1], grao[MAXN << 1];
int head[MAXN], heado[MAXN], ecnt, ecnto;

inline void addedge(int u, int v, int w) {
    gra[ecnt] = Edge {v, w, head[u]}; head[u] = ecnt++;
}

inline void addedgeo(int u, int v, int w) {
    grao[ecnto] = Edge {v, w, heado[u]}; heado[u] = ecnto++;
}

inline void rebuild(int u, int fa) {
    int ff = 0;
    for(int i = heado[u]; ~i; i = grao[i].nxt) {
        int v = grao[i].to, w = grao[i].w;
        if(v == fa) continue;
        if(!ff) {
            addedge(u, v, w);
            addedge(v, u, w);
            ff = u;
        } else {
            int k = ++n;
            col[k] = 1;
            addedge(ff, k, 0);
            addedge(k, ff, 0);
            addedge(k, v, w);
            addedge(v, k, w);
            ff = k;
        }
        rebuild(v, u);
    }
}

bool del[MAXN << 1];
int ct, ctsiz, sum;
int siz[MAXN], msz[MAXN];

inline void calsiz(int u, int fa) {
    siz[u] = 1;
    for(int i = head[u]; ~i; i = gra[i].nxt) {
        int v = gra[i].to;
        if(del[i >> 1] || v == fa) continue;
        calsiz(v, u);
        siz[u] += siz[v];
    }
}

inline void findct(int u, int fa) {
    for(int i = head[u]; ~i; i = gra[i].nxt) {
        int v = gra[i].to;
        if(del[i >> 1] || v == fa) continue;
        findct(v, u);
        int vsiz = std::max(siz[v], sum - siz[v]);
        if(vsiz < ctsiz) {
            ct = i;
            ctsiz = vsiz;
        }
    }
}

struct DisData {
    int u, d;
    inline bool operator<(const DisData &rhs) const {
        return d < rhs.d;
    }
};

std::priority_queue<DisData> s[MAXN][2];
int cnt;

struct NodeData {
    int bel, side, dis;
};
std::vector<NodeData> ndata[MAXN];

inline void caldis(int u, int fa, int d, int t, int l) {
    if(!col[u]) {
        s[t][l].push(DisData {u, d}); ndata[u].push_back(NodeData {t, l, d});
    }
    for(int i = head[u]; ~i; i = gra[i].nxt) {
        int v = gra[i].to, w = gra[i].w;
        if(del[i >> 1] || v == fa) continue;
        caldis(v, u, d + w, t, l);
    }
}

int mx[MAXN], lch[MAXN], rch[MAXN], ctw[MAXN];

inline void update(int p) {
    while(!s[p][0].empty() && col[s[p][0].top().u]) s[p][0].pop();
    while(!s[p][1].empty() && col[s[p][1].top().u]) s[p][1].pop();
    if(s[p][0].empty() || s[p][1].empty()) mx[p] = 0;
    else mx[p] = s[p][0].top().d + ctw[p] + s[p][1].top().d;
    if(lch[p]) mx[p] = std::max(mx[p], mx[lch[p]]);
    if(rch[p]) mx[p] = std::max(mx[p], mx[rch[p]]);
}

inline int divide(int u) {
    calsiz(u, 0);
    ct = -1; ctsiz = INF; sum = siz[u]; findct(u, 0);
    if(ct == -1) return 0;
    int x = gra[ct].to, y = gra[ct ^ 1].to;
    del[ct >> 1] = true;
    int t = ++cnt;
    ctw[t] = gra[ct].w;
    caldis(x, 0, 0, t, 0); caldis(y, 0, 0, t, 1);
    lch[t] = divide(x); rch[t] = divide(y); 
    update(t);
    return t;
}

inline void setwhite(int u) {
    for(int i = ndata[u].size() - 1; i >= 0; i--) {
        NodeData d = ndata[u][i];
        s[d.bel][d.side].push(DisData {u, d.dis});
        update(d.bel);
    }
}

inline void setblack(int u) {
    for(int i = ndata[u].size() - 1; i >= 0; i--) {
        NodeData d = ndata[u][i];
        update(d.bel);
    }
}

int ut, vt, wt;
char op;

int main() {
    memset(head, -1, sizeof(head));
    memset(heado, -1, sizeof(heado));
    n = readint();
    int white = n;
    for(int i = 1; i < n; i++) {
        ut = readint(); vt = readint(); wt = readint();
        addedgeo(ut, vt, wt);
        addedgeo(vt, ut, wt);
    }
    rebuild(1, 0);
    divide(1);
    q = readint();
    while(q--) {
        op = readop();
        if(op == 'A') {
            if(!white) {
                puts("They have disappeared.");
            } else if(white == 1) {
                puts("0");
            } else {
                printf("%d\n", mx[1]);
            }
        } else {
            ut = readint(); 
            col[ut] ^= 1;
            if(col[ut]) {
                setblack(ut);
                white--;
            } else {
                setwhite(ut);
                white++;
            }
        }
    }
    return 0;
}
[国家集训队]聪聪可可 题解

[国家集训队]聪聪可可 题解

题目地址:洛谷:【P2634】[国家集训队]聪聪可可 – 洛谷、BZOJ:Problem 2152. — 聪聪可可

题目描述

聪聪和可可是兄弟俩,他们俩经常为了一些琐事打起来,例如家中只剩下最后一根冰棍而两人都想吃、两个人都想玩儿电脑(可是他们家只有一台电脑)……遇到这种问题,一般情况下石头剪刀布就好了,可是他们已经玩儿腻了这种低智商的游戏。
他们的爸爸快被他们的争吵烦死了,所以他发明了一个新游戏:由爸爸在纸上画n个“点”,并用n-1条“边”把这n个“点”恰好连通(其实这就是一棵树)。并且每条“边”上都有一个数。接下来由聪聪和可可分别随即选一个点(当然他们选点时是看不到这棵树的),如果两个点之间所有边上数的和加起来恰好是3的倍数,则判聪聪赢,否则可可赢。
聪聪非常爱思考问题,在每次游戏后都会仔细研究这棵树,希望知道对于这张图自己的获胜概率是多少。现请你帮忙求出这个值以验证聪聪的答案是否正确。

输入输出格式

输入格式:
输入的第1行包含1个正整数n。后面n-1行,每行3个整数x、y、w,表示x号点和y号点之间有一条边,上面的数是w。

输出格式:
以即约分数形式输出这个概率(即“a/b”的形式,其中a和b必须互质。如果概率为1,输出“1/1”)。

输入输出样例

输入样例#1:

5
1 2 1
1 3 2
1 4 1
2 5 3

输出样例#1:

13/25

题解

直接把距离、边权对3取模存起来,这样可以减少模运算的次数,优化常数。
统计一个子树下点的距离对3取余为0、1、2的点有多少,答案即c_0^2 + 2c_1c_2(距离被3整除的点之间以及和根,距离余3为1、2的点互相构成点对)。然后把不合法方案减掉,套个gcd,就解决了。

代码

// Code by KSkun, 2018/3
#include <cstdio>

inline int max(int a, int b) {
    return a > b ? a : b;
} 

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}

inline int readint() {
    register int res = 0, neg = 1;
    char c = fgc();
    while(c < '0' || c > '9') {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(c >= '0' && c <= '9') {
        res = res * 10 + c - '0';
        c = fgc();
    }
    return res * neg;
}

const int MAXN = 20005, INF = 1e9;

int n, m, ut, vt, wt, k, rt, res = 0;
int siz[MAXN], dep[MAXN], msz[MAXN], sum;
bool vis[MAXN];

struct Edge {
    int to, w, nxt;
} gra[MAXN << 1];
int head[MAXN], tot = 0;

inline void addedge(int u, int v, int w) {
    tot++;
    gra[tot].to = v;
    gra[tot].w = w;
    gra[tot].nxt = head[u];
    head[u] = tot;
}

int c[3];

inline void getroot(int u, int fa) {
    siz[u] = 1;
    msz[u] = 0; 
    for(int i = head[u]; i; i = gra[i].nxt) {
        int v = gra[i].to;
        if(vis[v] || v == fa) continue;
        getroot(v, u);
        siz[u] += siz[v];
        msz[u] = max(msz[u], siz[v]);
    }
    msz[u] = max(msz[u], sum - siz[u]);
    if(msz[u] < msz[rt]) rt = u;
}

inline void caldep(int u, int fa) {
    c[dep[u]]++;
    for(int i = head[u]; i; i = gra[i].nxt) {
        int v = gra[i].to, w = gra[i].w;
        if(vis[v] || v == fa) continue;
        dep[v] = (dep[u] + w) % 3;
        caldep(v, u); 
    }
}

inline int work(int u, int w) {
    c[0] = c[1] = c[2] = 0;
    dep[u] = w;
    caldep(u, 0);
    return c[0] * c[0] + c[1] * c[2] * 2;
}

inline void dfs(int u) {
    res += work(u, 0);
    vis[u] = true;
    for(int i = head[u]; i; i = gra[i].nxt) {
        int v = gra[i].to, w = gra[i].w;
        if(vis[v]) continue;
        res -= work(v, w);
        rt = 0;
        sum = siz[v];
        getroot(v, 0);
        dfs(rt);
    }
}

inline int gcd(int a, int b) {
    int t;
    while(t = a % b) {
        a = b; b = t;
    }
    return b;
}

int main() {
    n = readint();
    for(int i = 1; i < n; i++) {
        ut = readint(); vt = readint(); wt = readint() % 3;
        addedge(ut, vt, wt);
        addedge(vt, ut, wt);
    }
    rt = 0;
    msz[0] = INF;
    sum = n;
    getroot(1, 0);
    dfs(rt);
    int t1 = n * n, t2 = gcd(res, t1);
    printf("%d/%d", res / t2, t1 / t2);
    return 0;
}