分治

本篇重点讲三个东西，线段树分治，点分治，以及CDQ分治。

TOP1 线段树分治

  • 这个算法主要是针对于一些对在线算法很不友好的题，其模型大概是维护一张图，其中的边在某个固定时刻存在，其余时刻不存在，并在某些时刻让你针对于那个时刻的图做一些询问。
  • 确实一听就很恶心,你总不能全靠\(LCT\)
  • 所以这个基于时间轴来分治的线段树分治就有了，其实如果看过线段树优化建图的话，这个就非常好理解了,具体来讲就是把操作和询问离线下来，对于每条边所覆盖的时间区间打上标记，在从根向那个时间搜的时候，一边dfs一边就把当时有的边建了出来，在搜到叶子节点时处理答案，回溯的时候将建的边撤销，这时就得用上可撤销并查集了(其实就是不路径压缩的按秩合并存一下连边前状态)。然后这个线段树分治就做完了。
  • 当然，我们离线下来的轴不一定是时间，类似的只要是基于某个轴的操作都可以进行。
  • 例题推荐的话P5787
    这个针灸纯板子,就是用了一个扩展域并查集查二分图的\(trick\)
here 


#include <bits/stdc++.h>


#define LL long long
#define Re register int
#define LD double
#define mes(x, y) memset(x, y, sizeof(x))
#define cpt(x, y) memcpy(x, y, sizeof(x))
#define fuc(x, y) inline x y
#define fr(x, y, z)for(Re x = y; x <= z; ++ x)
#define fp(x, y, z)for(Re x = y; x >= z; -- x)
#define delfr(x, y, z)for(Re x = y; x < z; ++ x)
#define delfp(x, y, z)for(Re x = y; x > z; -- x)
#define frein(x) freopen(#x ".in", "r", stdin)
#define freout(x) freopen(#x ".out", "w", stdout)
#define ki putchar('\n')
#define fk putchar(' ')
#define WMX aiaiaiai~~
#define mk(x, y) make_pair(x, y)
#define pb(x) push_back(x)
#define re(x) return x
#define sec second
#define fst first
using namespace std;
namespace kiritokazuto{
    auto read = [](){
        LL x = 0;
        int f = 1;
        char c;
        while (!isdigit(c = getchar())){ if (c == '-')f = -1; }
        do{ x = (x << 1) + (x << 3) + (c ^ 48); } while (isdigit(c = getchar()));
        return x * f;
    };
    template <typename T> fuc(void, write) (T x){
        if (x < 0)putchar('-'), x = -x;
        if (x > 9)write(x / 10);putchar(x % 10 | '0');
    }

}

using namespace kiritokazuto;
const int maxn = 2e6 + 10, Inf = 0x3f3f3f3f, Mod = 5000007;


int n, m, k;
int heigh[maxn << 1];
struct EDGE{int from, to;}wmx[maxn];
struct STK{int x, y, hig;}stk[maxn];
int top = 0;
int fa[maxn << 1];
struct Set_Union {
    fuc(void, init)(){fr(i, 1, n << 1)fa[i] = i, heigh[i] = 1;}
    fuc(int , find)(int x) {while(x != fa[x])x = fa[x]; return x;}
    fuc(void, merge)(int x, int y) {
        x = find(x), y = find(y);
        if(heigh[x] > heigh[y])swap(x, y);
        fa[x] = y;
        stk[++top] = (STK){x, y, heigh[x] == heigh[y]};
        heigh[y] += (heigh[x] == heigh[y]);
    }
}F;
struct Seg_Tree {
    #define lsp(rt) (rt << 1)
    #define rsp(rt) (rt << 1 | 1)
    #define mid ((l + r) >> 1)
    vector <int> vec[maxn];
    fuc(void, insert)(int rt, int l, int r, int L, int R, int val) {
        if(L <= l && r <= R) {return vec[rt].pb(val), void();}
        if(L <= mid)insert(lsp(rt), l, mid, L, R, val);
        if(R > mid)insert(rsp(rt), mid + 1, r, L, R, val);
    }
    fuc(void, query)(int rt, int l, int r) {
        int is = 1, sz = vec[rt].size();
        int lst = top;

        delfr(i, 0, sz) {
            int pos = vec[rt][i];
            int from = wmx[pos].from, to = wmx[pos].to;
            int ffrom = F.find(from), fto = F.find(to);
            if(ffrom != fto) {
                F.merge(from, to + n);
                F.merge(to, from + n);
            }else {
                is = 0;
                fr(j, l, r) {
                    puts("No");
                }
                break;
            }
        }
        if(is && l == r) puts("Yes");
        if(is && l != r) query(lsp(rt), l, mid), query(rsp(rt), mid + 1, r);
        while(top > lst) {
            int x = stk[top].x;
            int y = stk[top].y;
            heigh[y] -= stk[top].hig;
            fa[x] = x;
            top--;
        }
    }
}T;

signed main(){
    n = read(), m = read(), k = read();
    F.init();
    fr(i, 1, m) {
        int x = read(), y = read(), l = read(), r = read();
        wmx[i].from = x, wmx[i].to = y;
        T.insert(1, 1, k, l + 1, r, i);//有0时刻没用
    }
    T.query(1, 1, k);
    
}
  • 其余的还有地理课，\(No Rest for the Wicked\) 等

TOP2 点分治

  • 这个吧，确实是个暴力

  • 它主要用于处理一些单次的对树上某些问题的询问(多次的可以通过点分树实现)，具体的模型有距离为\(K\)的点对存在与否，距离\(\le K\)的点对存在多少等等，模型很多，自己摸索。

  • 分治分治，肯定就是分开干嘛。

    • 那么我们首先就可以将一颗树看成无根树，任意钦定一个点为根，然后对于询问大力分讨:
      • 点对间的路径经过当前根。
      • 点对间的路径不经过当前根。
    • 对于经过的，我们可以将树看成一颗二叉树，具体的，递归遍历每一颗子树，存下它内部与根构成的对答案有贡献的信息，并和前边已经遍历过的子树的答案相匹配构成答案，之后将它合并到已经遍历过的子树那一支。
    • 对于不经过的，那么它显然会经过我子树里的某个节点，那么好办分治嘛，我把我这个根删了，去我子树里再进行这两步操作就\(ok\)了，显然一听就很有正确性嘛。

  • 但是，这玩意的复杂度还是不显示，如果是一条链，这不显然是暴力…所以考虑优化——我们每次找树的重心作根。。。然后树高就限制在了\(\log n\)层上，然后，它就从暴力变成正解了，其实因为这个性质，我们可以对它做到很多其他树上做不到的操作，然后他就很优秀了，模型复杂度是\(O(n \log n)\)的,但有时候用数据结构，或者是(科技FFT)优化它，可能会多出一些$\log $等等。

  • 注意事项

    • 尽量在清空当前子树存的信息时别用memset会\(TLE\)
    • 重心一定要找对，找对，找对!!!!!

  • 例题的话

  • P2634这个题显然维护一下余数就好了，很水。

here 


#include <bits/stdc++.h>
#define LL long long
#define Re register int
#define LD double
#define mes(x, y) memset(x, y, sizeof(x))
#define fuc(x, y) inline x y
#define fr(x, y, z)for(Re x = y; x <= z; ++ x)
#define fp(x, y, z)for(Re x = y; x >= z; -- x)
#define delfr(x, y, z)for(Re x = y; x < z; ++ x)
#define delfp(x, y, z)for(Re x = y; x > z; -- x)
#define frein(x) freopen(#x ".in", "r", stdin)
#define freout(x) freopen(#x ".out", "w", stdout)
#define ki putchar('\n')
#define fk putchar(' ')
#define WMX aiaiaiai~~
#define mk(x, y) make_pair(x, y)
#define pb(x) push_back(x)
#define sec second
#define fst first
 
using namespace std;
namespace kiritokazuto{
    // auto read = [](){
    //     LL x = 0;
    //     int f = 1;
    //     char c;
    //     while (!isdigit(c = getchar())){ if (c == '-')f = -1; }
    //     do{ x = (x << 1) + (x << 3) + (c ^ 48); } while (isdigit(c = getchar()));
    //     return x * f;
    // };
    inline char getc(){
        static char buf[1<<18],*p1,*p2;
        if(p1==p2){p1=buf,p2=buf+fread(buf,1,1<<18,stdin);if(p1==p2)return EOF;}
        return *p1++;
    }
    inline LL read(){
        LL x=0;char ch=getc();
        while(!isdigit(ch))ch=getc();
        while(isdigit(ch))x=(x<<1)+(x<<3)+(ch^48),ch=getc();
        return x;
    }
    template <typename T> fuc(void, write) (T x){
        if (x < 0)putchar('-'), x = -x;
        if (x > 9)write(x / 10);putchar(x % 10 | '0');
    }
 
}   
 
using namespace kiritokazuto;
const int maxn = 1e6 + 200, Inf = 0x3f3f3f3f, Mod = 5000007;
int x, y, rt, Min = Inf, len = 0, sum;
LL w, dis[maxn], ans, n;
int sz[maxn], head[maxn], rem[maxn], tmp[maxn], exist[maxn];//很显然存余数
bool vis[maxn];
struct Node{int to, next; LL dis; Node(){}; Node(int x, int y, LL z){to = x, next = y, dis = z;};}wmx[maxn << 1];
fuc(void, Qian)(int from, int to, int dis) {wmx[++len] = (Node){to, head[from], dis}; head[from] = len;}
struct Point_div{
    fuc(void, find_rt)(int x, int fa) {
        sz[x] = 1; int res = -1;
        for(Re i = head[x]; i; i = wmx[i].next) {
            int to = wmx[i].to;
            if(vis[to] || to == fa)continue;
            find_rt(to, x);
            sz[x] += sz[to];
            res = max(res, sz[to]);
        }
        res = max(res, sum - sz[x]);
        if(res < Min) {
            Min = res;
            rt = x;
        }
    }
    fuc(void, get_dis)(int x, int fa) {
        // exist[dis[x] % 3] ++;
        rem[dis[x] % 3] ++;
        for(Re i = head[x]; i; i = wmx[i].next) {
            int to = wmx[i].to;
            if(vis[to] || to == fa)continue;
            dis[to] = dis[x] + wmx[i].dis;
            get_dis(to, x);
        }
    }
    fuc(void, calc)(int x) {
        exist[0] = 1;
        for(Re i = head[x]; i; i = wmx[i].next) {
            int to = wmx[i].to;
            if(vis[to])continue;
            rem[0] = 0;
            dis[to] = wmx[i].dis;
            fr(j, 0, 2)rem[j] = 0;
            get_dis(to, x);
            // fr(j, 0, 2) {
            //     printf("x = %d rem[%d] = %d exist[%d] = %d\n", x, j, rem[j], j, exist[j]);
            // }
            
            fr(j, 0, 2) {
                // if(j == 0)ans += max(rem[j], exist[j]);
                // else ans += max(rem[j], exist[3 - j]);
                if(j == 0)  {
                    if(exist[j] != 0 && rem[j] != 0)ans += rem[j] * exist[j];
                }else if(rem[j] != 0 && exist[3 - j] != 0) ans += rem[j] * exist[3 - j];
                
            }
            // printf("x = %d ans = %d\n", x, ans);
            // ki;
            fr(j, 0, 2){
                exist[j] += rem[j];
            }
        }
        fr(i, 0, 2)exist[i] = 0;
    }   
    fuc(void, solve)(int x) {
        vis[x] = 1;calc(x);
        for(Re i = head[x]; i; i = wmx[i].next) {
            int to = wmx[i].to;
            if(vis[to])continue;
            sum = sz[to], Min = Inf;
            // cerr << "oldrt = " << rt << "\n";
            find_rt(to, 0);
            // cerr << "newrt = " << rt << "\n";
            solve(rt);
        }
    }
}T;
//首先考虑总情况
//n * (n - 1) / 2 * 2 + n = n ^ 2

signed main(){
    n = read();
    delfr(i, 1, n) {
        x = read(), y = read(), w = read();
        Qian(x, y, w);
        Qian(y, x, w);
    }
    sum = n, Min = Inf;
    T.find_rt(1, 0);
    T.solve(rt);
    ans = ans * 2 + n;
    n = n * n;
    while(__gcd(ans, n) != 1) {
        int tmp = __gcd(ans, n);
        ans /= tmp;
        n /= tmp;
    }
    printf("%d/%d\n", ans, n);
    return 0;   
}
  • P4149这个题用个pair存一下就行，也是板子
here 


#include <bits/stdc++.h>
#define LL long long
#define Re register int
#define LD double
#define mes(x, y) memset(x, y, sizeof(x))
#define fuc(x, y) inline x y
#define fr(x, y, z)for(Re x = y; x <= z; ++ x)
#define fp(x, y, z)for(Re x = y; x >= z; -- x)
#define delfr(x, y, z)for(Re x = y; x < z; ++ x)
#define delfp(x, y, z)for(Re x = y; x > z; -- x)
#define frein(x) freopen(#x ".in", "r", stdin)
#define freout(x) freopen(#x ".out", "w", stdout)
#define ki putchar('\n')
#define fk putchar(' ')
#define WMX aiaiaiai~~
#define mk(x, y) make_pair(x, y)
#define pb(x) push_back(x)
#define sec second
#define fst first
 
using namespace std;
namespace kiritokazuto{
    // auto read = [](){
    //     LL x = 0;
    //     int f = 1;
    //     char c;
    //     while (!isdigit(c = getchar())){ if (c == '-')f = -1; }
    //     do{ x = (x << 1) + (x << 3) + (c ^ 48); } while (isdigit(c = getchar()));
    //     return x * f;
    // };
    inline char getc(){
        static char buf[1<<18],*p1,*p2;
        if(p1==p2){p1=buf,p2=buf+fread(buf,1,1<<18,stdin);if(p1==p2)return EOF;}
        return *p1++;
    }
    inline LL read(){
        LL x=0;char ch=getc();
        while(!isdigit(ch))ch=getc();
        while(isdigit(ch))x=(x<<1)+(x<<3)+(ch^48),ch=getc();
        return x;
    }
    template <typename T> fuc(void, write) (T x){
        if (x < 0)putchar('-'), x = -x;
        if (x > 9)write(x / 10);putchar(x % 10 | '0');
    }
 
}   
 
using namespace kiritokazuto;
const int maxn = 1e6 + 200, Inf = 0x3f3f3f3f, Mod = 5000007;
int n, m, len = 0, rt, Min = Inf, sum, cnt, tot, ans = Inf;
int exMin[maxn], head[maxn], sz[maxn], vis[maxn], tmp[maxn], dis[maxn];
pair <int, int> rem[maxn];
struct Node{int to, next; LL dis; Node(){}; Node(int x, int y, LL z){to = x, next = y, dis = z;};}wmx[maxn << 1];
fuc(void, Qian)(int from, int to, int dis) {wmx[++len] = (Node){to, head[from], dis}; head[from] = len;}
struct Point_div{
    fuc(void, find_rt)(int x, int fa) {
        sz[x] = 1;int res = -1;
        for(Re i = head[x]; i; i = wmx[i].next) {
            int to = wmx[i].to;
            if(vis[to] || to == fa)continue;
            find_rt(to, x);
            sz[x] += sz[to];
            res = max(res, sz[to]);
        }
        res = max(res, sum - sz[x]);
        if(res < Min) {
            Min = res;
            rt = x;
        }
    }
    fuc(void, get_dis)(int x, int fa, int num) {
        if(dis[x] > m)return;
        rem[++cnt] = mk(dis[x], num);
        for(Re i = head[x]; i; i = wmx[i].next) {
            int to = wmx[i].to;
            if(vis[to] || to == fa)continue;
            dis[to] = dis[x] + wmx[i].dis;
            // puts("KKK");
            // cerr << "KKK x = "<< x << " to = " << to << " dis[to] = " << dis[to] << " \n";
            get_dis(to, x, num + 1);
        }
    }
    fuc(void, calc)(int x) {
        tot = 0;
        exMin[0] = 0;
        // cerr << "rtx = " << x << "\n";
        for(Re i = head[x]; i; i = wmx[i].next) {
            int to = wmx[i].to;
            if(vis[to])continue;
            dis[to] = wmx[i].dis;
            cnt = 0;
            get_dis(to, x, 1);
            // delfr(j, 0, n) {
                // cerr << "x = "<< x << " j = " << j << " dis[j] = " << dis[j] << " \n";
                // cerr << rem[j].fst << " " << rem[j].sec << "!!!!!!" << "\n";
            // }
            // fr(j, 1, cnt) {
            //      cerr << rem[j].fst << " " << rem[j].sec << " !!!!!!" << "\n";
            // }
            fr(j, 1, cnt) if(m >= rem[j].fst) ans = min(ans, exMin[m - rem[j].fst] + rem[j].sec);
            fr(j, 1, cnt) {
                tmp[++tot] = rem[j].fst;
                exMin[rem[j].fst] = min(exMin[rem[j].fst], rem[j].sec);
            }
        }
        fr(j, 1, tot)exMin[tmp[j]] = Inf;
    }
    fuc(void, solve)(int x) {
        vis[x] = 1;calc(x);
        // cerr << x << " ls " << " vis[x] " << vis[x] << "\n";
        for(Re i = head[x]; i; i = wmx[i].next) {
            int to = wmx[i].to;
            if(vis[to])continue;
            sum = sz[to], Min = Inf, rt = 0;
            find_rt(to, 0);
            // cerr <<"KKK = " << rt << "\n";
            solve(rt);
        }
    }
}T;
signed main(){
    n = read(), m = read();
    delfr(i, 1, n) {
        int x = read() + 1, y = read() + 1;
        LL z = read();
        Qian(x, y, z);
        Qian(y, x, z);
    }
    sum = n, Min = Inf;
    T.find_rt(1, 0);
    // cerr << rt << "\n";
    mes(exMin, 0x3f);
    T.solve(rt);
    write(ans >= n ? -1 : ans);
    return 0;   
}
  • P4178这个就是数据结构优化了一下，用树状数组维护一下前缀和就行。
here 


#include <bits/stdc++.h>
#define LL long long
#define Re register int
#define LD double
#define mes(x, y) memset(x, y, sizeof(x))
#define fuc(x, y) inline x y
#define fr(x, y, z)for(Re x = y; x <= z; ++ x)
#define fp(x, y, z)for(Re x = y; x >= z; -- x)
#define delfr(x, y, z)for(Re x = y; x < z; ++ x)
#define delfp(x, y, z)for(Re x = y; x > z; -- x)
#define frein(x) freopen(#x ".in", "r", stdin)
#define freout(x) freopen(#x ".out", "w", stdout)
#define ki putchar('\n')
#define fk putchar(' ')
#define WMX aiaiaiai~~
#define mk(x, y) make_pair(x, y)
#define pb(x) push_back(x)
#define sec second
#define fst first
 
using namespace std;
namespace kiritokazuto{
    // auto read = [](){
    //     LL x = 0;
    //     int f = 1;
    //     char c;
    //     while (!isdigit(c = getchar())){ if (c == '-')f = -1; }
    //     do{ x = (x << 1) + (x << 3) + (c ^ 48); } while (isdigit(c = getchar()));
    //     return x * f;
    // };
    inline char getc(){
        static char buf[1<<18],*p1,*p2;
        if(p1==p2){p1=buf,p2=buf+fread(buf,1,1<<18,stdin);if(p1==p2)return EOF;}
        return *p1++;
    }
    inline LL read(){
        LL x=0;char ch=getc();
        while(!isdigit(ch))ch=getc();
        while(isdigit(ch))x=(x<<1)+(x<<3)+(ch^48),ch=getc();
        return x;
    }
    template <typename T> fuc(void, write) (T x){
        if (x < 0)putchar('-'), x = -x;
        if (x > 9)write(x / 10);putchar(x % 10 | '0');
    }
 
}   
 
using namespace kiritokazuto;
const int maxn = 1e5 + 10, Inf = 2147483647, Mod = 1e9 + 7;
// #define int long long
int n, q, m;
int rt, Min = Inf, sum;
int sz[maxn];
int head[maxn], len = 0;
struct Node {
    int to, next, dis;
}wmx[maxn << 1];
fuc(void, Qian)(int from, int to, int dis) {
    wmx[++len].to = to;
    wmx[len].next = head[from];
    wmx[len].dis = dis;
    head[from] = len;
}
struct BIT {
    int tr[maxn];
    fuc(void, updata)(int x, int val) {
        if(x == 0)return tr[0]++, void();
        while(x <= m) {
            tr[x] += val;
            x += x & (-x);
        }
    }
    fuc(int, query)(int x) {
        if(x == 0)return tr[0];
        int res = tr[0];
        while(x) {
            res += tr[x];
            x -= x & (-x);
        }
        return res;
    }
}Bit;
int vis[maxn];
int rem[maxn];
int tmp[maxn], cnt = 0;
int ans;
int dis[maxn];
struct Point_div {
    fuc(void , get_rt)(int x, int pre){
        sz[x] = 1;
        int res = -1;
        for(Re i = head[x]; i; i = wmx[i].next) {
            int to = wmx[i].to;
            if(vis[to] || to == pre)continue;
            get_rt(to, x);
            sz[x] += sz[to];
            res = max(res, sz[to]);
        }
        res = max(res, sum - sz[x]);
        if(res < Min) {
            Min = res;
            rt = x;
        }
    }
    fuc(void, get_dis)(int x, int pre ){
        rem[++rem[0]] = dis[x];
        for(Re i = head[x]; i; i = wmx[i].next) {
            int to = wmx[i].to;
            if(vis[to] || to == pre)continue;
            dis[to] = dis[x] + wmx[i].dis;
            get_dis(to, x);
        }
    }
    fuc(void, calc)(int x) {
        cnt = 0;
        for(Re i = head[x]; i; i = wmx[i].next) {
            int to = wmx[i].to;
            if(vis[to])continue;
            rem[0] = 0;
            dis[to] = wmx[i].dis;
            get_dis(to, x);
            // cerr << "Re 4" << "\n";
            fr(j, 1, rem[0]) {
                if(m >= rem[j])ans += Bit.query(m - rem[j]);
            }
            fr(j, 1, rem[0]) {
                if(rem[j] > m)continue;
                tmp[++cnt] = rem[j];
                Bit.updata(rem[j], 1);
            }
        } 
        fr(i, 1, cnt)Bit.updata(tmp[i], -1);
    }
    fuc(void, solve)(int x) {
        vis[x] = Bit.tr[0] = 1;
        // cerr << "Re 2" << "\n";
        calc(x);
        // cerr << "Re 3" << "\n";
        for(Re i = head[x]; i; i = wmx[i].next) {
            int to = wmx[i].to;
            if(vis[to])continue;
            sum = sz[to], Min = Inf;
            get_rt(to, 0);
            solve(rt);
        } 
    }
}T;

signed main(){
    n = read();
    delfr(i, 1, n) {
        int x = read(), y = read(), z =read();
        Qian(x, y, z);
        Qian(y, x, z);
    }
    m = read();
    sum = n, Min = Inf;
    T.get_rt(1, 0);
    // cerr << "Re 1" << "\n";
    T.solve(rt);
    write(ans);
   return 0;
}
  • 采药人的路径(自己从网上搜吧),这个题确实有思维含量。

    • 是个类似树上\(dp\)形式的点分治，我们把\(0\)的边设置成\(-1\)，那么题意就转化为了找前缀和为\(0\)的树上路径，然后我们考虑休息站(这道题不管路上有几个休息站都是同一种方案，是按照起点和终点来确定方案的不同的)，然后我们发现如果有休息站的话，我们的休息站一定和我们两个端点其中之一前缀和相同(两个相同的一做差不就是\(0\)嘛，那么它到端点的前缀和不也是\(0\)了嘛)。

    • 所以我们记录\(rem[1/ 0][x]\)为当前子树内距离根节点为\(x\)的路径上,有\(or\)没有休息站的路径条数，然后我们和之前子树的匹配一下就好了,设记录之前子树的数组为\(tmp[1/ 0][x]\)

      \[ans += rem[0][j] * tmp[1][-j] + rem[1][j] * tmp[0][-j] + rem[1][j] * tmp[1][-j] \]

    • 也就是两边各有或者是都有。

    • 其他的就是注意我

      \[ans += rem[0][0] * tmp[0][0] \]

    • 两边为\(0\)的显然直接根就是休息站。

      \[ans += rem[1][0] \]

    • 递归一个子树时，直接和根组合。

    • 其余就是注意数组下标不能有负数，所以我们整体偏移一个\(n\)就行

here 


#include <bits/stdc++.h>
#define LL long long
#define Re register int
#define LD double
#define mes(x, y) memset(x, y, sizeof(x))
#define cpt(x, y) memcpy(x, y, sizeof(x))
#define fuc(x, y) inline x y
#define fr(x, y, z)for(Re x = y; x <= z; x ++)
#define fp(x, y, z)for(Re x = y; x >= z; x --)
#define delfr(x, y, z)for(Re x = y; x < z; x ++)
#define delfp(x, y, z)for(Re x = y; x > z; x --)
#define frein(x) freopen(#x ".in", "r", stdin)
#define freout(x) freopen(#x ".out", "w", stdout)
#define ki putchar('\n')
#define fk putchar(' ')
#define WMX aiaiaiai~~
#define pr(x, y) pair<x, y>
#define mk(x, y) make_pair(x, y)
#define pb(x) push_back(x)
#define re(x) return x
#define sec second
#define fst first
using namespace std;
namespace kiritokazuto{
    auto read = [](){
        LL x = 0;
        int f = 1;
        char c;
        while (!isdigit(c = getchar())){ if (c == '-')f = -1; }
        do{ x = (x << 1) + (x << 3) + (c ^ 48); } while (isdigit(c = getchar()));
        return x * f;
    };
    template  <typename T> fuc(void, write)(T x){
        if (x < 0)putchar('-'), x = -x;
        if (x > 9)write(x / 10); putchar(x % 10 | '0');
    }
}

using namespace kiritokazuto;

const int maxn = 2e5 + 100,  Mod = 998244353;
const LL Inf = 2147483647;
int head[maxn], exi[maxn << 1], sz[maxn], vis[maxn];
int len = 0, rt, Min = Inf, sum, n, x, y, z, Maxdep, Mindep = Inf, maxdep, mindep = Inf;
LL ans;
int rem[2][maxn << 1], tmp[2][maxn << 1], dis[maxn];
struct Node{int to, next, dis;}wmx[maxn];
fuc(void, Qian)(int from, int to, int dis){wmx[++len] = {to, head[from], dis};head[from] = len;}
struct Point_Tree {
    fuc(void, get_rt)(int x, int fa) {
        int res = -1;sz[x] = 1;
        for(Re i = head[x]; i; i = wmx[i].next) {
            int to = wmx[i].to;
            if(vis[to] || to == fa)continue;
            get_rt(to, x);
            sz[x] += sz[to];
            res = max(res, sz[to]);
        }
        res = max(res, sum - sz[x]);
        if(res < Min){Min = res, rt = x;}
    }
    fuc(void, get_dis)(int x, int fa) {
        rem[exi[dis[x] + n] ? 1 : 0][dis[x] + n] ++;
        //首次出现为0第二次以至于多次出现为1
        exi[dis[x] + n] ++;
        // cerr << "-> " << exi[dis[x] + n] << " \n";
        maxdep = max(dis[x], maxdep);
        mindep = min(dis[x], mindep);
        for(Re i = head[x]; i; i = wmx[i].next) {
            int to = wmx[i].to;
            if(vis[to] || to == fa)continue;
            dis[to] = dis[x] + wmx[i].dis;
            get_dis(to, x);
        }
        exi[dis[x] + n] --;
    }
    fuc(void, calc)(int x) {
        bool fg = 1;
        Maxdep = - n - 1, Mindep = n + 1;
        for(Re  i = head[x]; i; i = wmx[i].next) {
            int to = wmx[i].to;
            if(vis[to])continue;
            maxdep = -n - 1, mindep = n + 1;
            dis[to] = wmx[i].dis;
            get_dis(to, x);
            Maxdep = max(Maxdep, maxdep);
            Mindep = min(Mindep, mindep);
            if(fg){}else 
            {
                ans += 1ll * rem[0][n] * tmp[0][n];//两个前缀和为0的拼一起(其实自己就可以)
                fr(j, mindep + n, maxdep + n ) {
                    int tp = j - n;
                    ans += 1ll * rem[0][j] * tmp[1][n - tp] + 1ll * rem[1][j] * tmp[0][n - tp] + 1ll * rem[1][j] * tmp[1][n - tp];
                }
            }
            ans += 1ll * rem[1][n];//自己拼一个0
            fg = 0;
            fr(j, mindep + n, maxdep + n) {
                tmp[0][j] += rem[0][j];
                tmp[1][j] += rem[1][j];
                rem[0][j] = rem[1][j] = exi[i] = 0;
            }
        }
        fr(j, Mindep + n, Maxdep + n){
            tmp[0][j] = tmp[1][j] = 0;
        }
    }
    fuc(void, solve)(int x) {
        vis[x] = 1;calc(x);
        for(Re i = head[x]; i; i = wmx[i].next) {
            int to = wmx[i].to;
            if(vis[to])continue;
            sum = sz[to], Min = Inf;
            get_rt(to, 0);
            // cerr << "2rt = " << rt << " \n";
            solve(rt);     
        }
    }
}T;

signed main() {
    n = read();
    delfr(i, 1, n) {
        x = read(), y = read(), z = (read() ? 1 : -1);
        Qian(x, y, z);
        Qian(y, x, z);
    } 
    sum = n, Min = Inf;
    T.get_rt(1, 0);
    // cerr << "1rt = " << rt << " \n";
    T.solve(rt);
    write(ans);
}

原文地址：http://www.cnblogs.com/kiritokazuto/p/16793516.html

1. 本站所有资源来源于用户上传和网络，如有侵权请邮件联系站长！ 2. 分享目的仅供大家学习和交流，请务用于商业用途! 3. 如果你也有好源码或者教程，可以到用户中心发布，分享有积分奖励和额外收入！ 4. 本站提供的源码、模板、插件等等其他资源，都不包含技术服务请大家谅解！ 5. 如有链接无法下载、失效或广告，请联系管理员处理！ 6. 本站资源售价只是赞助，收取费用仅维持本站的日常运营所需！ 7. 如遇到加密压缩包，默认解压密码为"gltf",如遇到无法解压的请联系管理员！ 8. 因为资源和程序源码均为可复制品，所以不支持任何理由的退款兑现，请斟酌后支付下载 声明：如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性