题面

如今,路由器和交换机构建起了互联网的骨架。处在互联网的骨干位置的
核心路由器典型的要处理100Gbit/s的网络流量。他们每天都生活在巨大的压力
之下。
小强建立了一个模型。这世界上有N个网络设备,他们之间有M个双向的
链接。这个世界是连通的。在一段时间里,有Q个数据包要从一个网络设备发
送到另一个网络设备。
一个网络设备承受的压力有多大呢?很显然,这取决于Q个数据包各自走
的路径。不过,某些数据包无论走什么路径都不可避免的要通过某些网络设
备。
你要计算:对每个网络设备,必须通过(包括起点、终点)他的数据包有
多少个?

题解

圆方树板题，直接求点双建出圆方树然后树链剖分线段树就行了。

CODE

#include <vector>
#include <queue>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
inline void read(int &num) {
    char ch; int flg=1; while(!isdigit(ch=getchar()))if(ch=='-')flg=-flg;
    for(num=0; isdigit(ch); num=num*10+ch-'0',ch=getchar()); num*=flg;
}
const int MAXN = 100005;
const int INF = 1e9;
int n, m, q, tot, w[MAXN], dfn[MAXN<<1], tmr, stk[MAXN], indx;
vector<int> e[MAXN];
struct Heap {
    priority_queue<int, vector<int>, greater<int> >A, B;
    inline void insert(int x) { A.push(x); }
    inline void erase(int x) { B.push(x); }
    inline int top() {
        while(!B.empty() && A.top() == B.top()) A.pop(), B.pop();
        return A.empty() ? INF : A.top();
    }
}W[MAXN];
int fir[MAXN<<1], to[MAXN<<2], nxt[MAXN<<2], cnt;
inline void add(int u, int v) {
    to[cnt] = v; nxt[cnt] = fir[u]; fir[u] = cnt++;
}
int tarjan(int u, int fa) {
    int lowu = dfn[u] = ++tmr;
    stk[++indx] = u;
    for(int v, lowv, i = 0, siz = e[u].size(); i < siz; ++i)
        if(!dfn[v=e[u][i]]) {
            lowu = min(lowu, lowv=tarjan(v, u));
            if(lowv >= dfn[u]) {
                fir[++tot] = -1;
                do {
                    W[tot-n].insert(w[stk[indx]]), add(tot, stk[indx]);
                }while(stk[indx--] != v);
                add(u, tot);
            }
        }
        else if(v != fa) lowu = min(lowu, dfn[v]);
    return lowu;
}
int dep[MAXN<<1], fa[MAXN<<1], sz[MAXN<<1], top[MAXN<<1], son[MAXN<<1], seq[MAXN<<1];
void dfs(int u, int ff) {
    dep[u] = dep[fa[u]=ff] + (sz[u]=1);
    for(int v, i = fir[u]; ~i; i = nxt[i]) {
        dfs(v=to[i], u), sz[u] += sz[v];
        if(sz[v] > sz[son[u]]) son[u] = v;
    }
}
void dfs2(int u, int tp) {
    top[u] = tp; seq[dfn[u] = ++tmr] = u;
    if(son[u]) dfs2(son[u], tp);
    for(int v, i = fir[u]; ~i; i = nxt[i])
        if((v=to[i]) != son[u]) dfs2(v, v);
}
int lz[MAXN<<3];
inline void pd(int i) {
    if(lz[i]) {
        lz[i<<1] += lz[i];
        lz[i<<1|1] += lz[i];
        lz[i] = 0;
    }
}
void modify(int i, int l, int r, int x, int y) {
    if(x <= l && r <= y) { lz[i] += 1; return; }
    pd(i);
    int mid = (l + r) >> 1;
    if(x <= mid) modify(i<<1, l, mid, x, y);
    if(y > mid) modify(i<<1|1, mid+1, r, x, y);
}
int query(int i, int l, int r, int x) {
    if(l == r) return lz[i];
    int mid = (l + r) >> 1;
    pd(i);
    if(x <= mid) return query(i<<1, l, mid, x);
    else return query(i<<1|1, mid+1, r, x);
}
inline void cover(int x, int y) {
    while(top[x] != top[y]) {
        if(dep[top[x]] < dep[top[y]]) swap(x, y);
        modify(1, 1, tot, dfn[top[x]], dfn[x]); x = fa[top[x]];
    }
    if(dep[x] > dep[y]) swap(x, y);
    modify(1, 1, tot, dfn[x], dfn[y]);
}
int main() {
    read(n), read(m), read(q); tot = n;
    for(int i = 1; i <= n; ++i) fir[i] = -1;
    for(int i = 1, x, y; i <= m; ++i)
        read(x), read(y), e[x].push_back(y), e[y].push_back(x);
    tarjan(1, 0); tmr = 0; dfs(1, 0); dfs2(1, 1);
    int x, y;
    while(q--)
        read(x), read(y), cover(x, y);
    for(int i = 1; i <= n; ++i)
        printf("%d\n", query(1, 1, tot, dfn[i]));
}

BZOJ 3331: [BeiJing2013]压力 （点双 圆方树 树链剖分 线段树）

原文：https://www.cnblogs.com/Orz-IE/p/12182779.html