BZOJ 3772: 精神污染 (dfs序+树状数组)

跟 ​​BZOJ 4009: [HNOI2015]接水果​​一样…

CODE

#include <set>
#include <queue>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
char cb[1<<15],*cs=cb,*ct=cb;
#define getc() (cs==ct&&(ct=(cs=cb)+fread(cb,1,1<<15,stdin),cs==ct)?0:*cs++)
template<class T>inline void read(T &res) {
    char ch; int flg = 1; for(;!isdigit(ch=getchar());)if(ch=='-')flg=-flg;
    for(res=ch-'0';isdigit(ch=getchar());res=res*10+ch-'0'); res*=flg;
}
const int MAXN = 100005;
struct node { int l, r, y, val; }a[MAXN<<2];
struct query { int x, y; }q[MAXN];
inline bool cmp(const node &A, const node &B) { return A.y < B.y; }
inline bool Cmp(const query &A, const query &B) { return A.y < B.y; } //zz写成了A.y<A.y调样例调了半天
int n, T[MAXN];
inline void upd(int x, int val) {
    while(x <= n) T[x] += val, x += x&-x;
}
inline int qsum(int x) { int re = 0;
    while(x) re += T[x], x -= x&-x;
    return re;
}

int m, tot, in[MAXN], out[MAXN], tmr, f[MAXN][17], dep[MAXN];
int fir[MAXN], to[MAXN<<1], nxt[MAXN<<1], cnt;
inline void Add(int u, int v) { to[++cnt] = v; nxt[cnt] = fir[u]; fir[u] = cnt; }
void dfs(int u) {
    in[u] = ++tmr; dep[u] = dep[f[u][0]] + 1;
    for(int i = 1; i < 17; ++i) f[u][i] = f[f[u][i-1]][i-1];
    for(int i = fir[u]; i; i = nxt[i])
        if(to[i] != f[u][0])
            f[to[i]][0] = u, dfs(to[i]);
    out[u] = tmr;
}
inline int find(int u, int v) {
    for(int j = 16; ~j; --j)
        if((dep[v]-dep[u]-1)&(1<<j))
            v = f[v][j];
    return v;
}
inline void insert(int minx, int maxx, int miny, int maxy) {
    a[++tot] = (node) { minx, maxx, miny, 1 };
    if(maxy < n) a[++tot] = (node) { minx, maxx, maxy+1, -1 };
}
int main () {
    read(n), read(m);
    for(int i = 1, x, y; i < n; ++i)
        read(x), read(y), Add(x, y), Add(y, x);
    dfs(1);
    for(int i = 1, x, y, z; i <= m; ++i) {
        read(x), read(y);
        if(in[x] > in[y]) swap(x, y);
        q[i].x=in[x], q[i].y=in[y];
        if(in[x] <= in[y] && out[y] <= out[x]) {
            z = find(x, y);
            insert(1, in[z]-1, in[y], out[y]);
            if(out[z] < n) insert(in[y], out[y], out[z]+1, n);
        }
        else insert(in[x], out[x], in[y], out[y]);
    }
    sort(a + 1, a + tot + 1, cmp);
    sort(q + 1, q + m + 1, Cmp);
    int cur = 1; LL ans = 0;
    for(int i = 1; i <= m; ++i) {
        while(cur <= tot && a[cur].y <= q[i].y) {
            upd(a[cur].l, a[cur].val), upd(a[cur].r+1, -a[cur].val);
            ++cur;
        }
        ans += qsum(q[i].x)-1;
    }
    LL all = 1ll*m*(m-1)/2;
    for(int i = 2; 1ll*i*i <= ans; ++i)
        while(all % i == 0 && ans % i == 0)
            all /= i, ans /= i;
    printf("%lld/%lld\n", ans, all);
}