DDOSvoid's Blog

noip 模拟赛 sum

发表于 分类于
本文字数： 2.8k 阅读时长 ≈ 3 分钟

题目描述

忘记是什么时候做的题了 = =

时间限制：2s

内存限制：256MB

【问题描述】

​ 有一颗n个节点的树。若删除其中任意一条边（不妨设为第k条边）后，i~j号节点都在同一联通块内，则记 $f[i][j][k]=1$

求 $\sum_{i=1}^n\sum_{j=i}^n\sum_{k=1}^{n-1}f[i][j][k]$

【输入】

输入文件名为sum.in。

​ 第一行一个数n

​ 接下来n-1行，每行两个数x,y描述一条边(1<=x,y<=n)

【输出】

输出文件名为sum.out。

​ 输出一个数，表示答案

【输入输出样例】

sum.in sum.out
3 1 2 1 3 7

【数据说明】

对于30%的数据，n<=100

对于50%的数据，n<=1000

对于100%的数据，n<=100000

Solution

注意到断一条边只会将树分成两个连通块

我们令每个点的状态为 $0$ 或 $1$，对于子树内和子树外的分别维护，问题转换为求连续的 $1$ 的贡献

注意到线段树可以维护这个贡献并且支持单点修改

所以我们考虑 $dsu$，注意到子树外的一大块和子树内的做法是一样的

时间复杂度 $O(n\log^2 n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include <iostream>
#include <cstdio>
#include <cstring>
#define maxn 100010
#define ll long long
#define cS const Seg
using namespace std;

int n;

struct Edge {
    int to, next;
} e[maxn * 2]; int c1, head[maxn];
inline void add_edge(int u, int v) {
    e[c1].to = v; e[c1].next = head[u]; head[u] = c1++;
}

inline ll F(ll x) { return x * (x - 1) / 2; } 

#define lc i << 1
#define rc i << 1 | 1
struct Segment_Tree { 
    struct Seg {
        int l, r; ll v; 
    } T[maxn * 4];

    inline Seg maintain(cS &ls, cS &rs, int l, int r) {
        Seg o; o.v = ls.v + rs.v; int m = l + r >> 1; 
        o.l = ls.l; o.r = rs.r;
        if(ls.r && rs.l)
            o.v = o.v - F(ls.r) - F(rs.l) + F(ls.r + rs.l);
        if(ls.l == m - l + 1 && rs.r == r - m) o.l = o.r = r - l + 1;
        else if(ls.l == m - l + 1) o.l += rs.l;
        else if(rs.r == r - m) o.r += ls.r;
        return o;
    }

    void update(int i, int l, int r, int k, int v) {
        if (l == r) return (void) (T[i].l = T[i].r = T[i].v = v);
        int m = l + r >> 1;
        if (k <= m) update(lc, l, m, k, v);
        else update(rc, m + 1, r, k, v);
        T[i] = maintain(T[lc], T[rc], l, r); 
    }

    void build(int i, int l, int r) {
        if (l == r) return (void) (T[i].l = T[i].r = T[i].v = 1);
        int m = l + r >> 1;
        build(lc, l, m); build(rc, m + 1, r); 
        T[i] = maintain(T[lc], T[rc], l, r); 
    } 

} T0, T1;

int son[maxn], sz[maxn], in[maxn], out[maxn], c2, bl[maxn];
void Dfs(int u, int fa) {
    int Max = 0; sz[u] = 1; in[u] = ++c2; bl[c2] = u;
    for (int i = head[u]; ~i; i = e[i].next) {
        int v = e[i].to; if (v == fa) continue ;
        Dfs(v, u); sz[u] += sz[v]; if (sz[v] > Max) Max = sz[v], son[u] = v;
    } out[u] = c2;
}

void add(int u) {
    for (int i = in[u], v = bl[i]; i <= out[u]; v = bl[++i]) 
        T0.update(1, 1, n, v, 1), T1.update(1, 1, n, v, 0);
}

void del(int u) {
    for (int i = in[u], v = bl[i]; i <= out[u]; v = bl[++i]) 
        T0.update(1, 1, n, v, 0), T1.update(1, 1, n, v, 1);
}

ll ans;
void dfs(int u, int fa) {
    for (int i = head[u]; ~i; i = e[i].next) {
        int v = e[i].to; if (v == fa || v == son[u]) continue;
        dfs(v, u); del(v);
    }
    if (son[u]) dfs(son[u], u);
    for (int i = head[u]; ~i; i = e[i].next) {
        int v = e[i].to; if (v == fa || v == son[u]) continue;
        add(v);
    }
    if (u == 1) return ;
    T0.update(1, 1, n, u, 1); T1.update(1, 1, n, u, 0);
    ans += T0.T[1].v + T1.T[1].v;
} 

int main() { memset(head, -1, sizeof head); 
    cin >> n; T1.build(1, 1, n);
    for (int i = 1; i < n; ++i) {
        int x, y; scanf("%d%d", &x, &y);
        add_edge(x, y); add_edge(y, x);
    } Dfs(1, 0); dfs(1, 0);
    cout << ans << endl; 
}