题意

略
题解

求路径上的割点。
然后就直接圆方树上差分
CODE

#include <bits/stdc++.h>

using namespace std;

inline void rd(int &x) {

    char ch; for(;!isdigit(ch=getchar()););

    for(x=ch-'0';isdigit(ch=getchar());)x=x*10+ch-'0';

}

const int MAXN = 100005;

const int MAXM = 200005;

int n, m, q;

int fir[MAXN], to[MAXM<<1], nxt[MAXM<<1], cnt = 1;

inline void link(int u, int v) {

    to[++cnt] = v; nxt[cnt] = fir[u]; fir[u] = cnt;

    to[++cnt] = u; nxt[cnt] = fir[v]; fir[v] = cnt;

}

int dfn[MAXN], low[MAXN], tmr, stk[MAXN], top, tot;

vector<int>G[MAXN<<1];

void tarjan(int u, int ff) {

    stk[++top] = u;

    low[u] = dfn[u] = ++tmr;

    for(int i = fir[u], v; i; i = nxt[i])

        if((i^1) != ff) {

            if(!dfn[v=to[i]]) {

                tarjan(v, i);

                low[u] = min(low[u], low[v]);

                if(low[v] >= dfn[u]) {

                    ++tot;

                    do G[tot].push_back(stk[top]), G[stk[top]].push_back(tot);

                    while(stk[top--] != v);

                    G[tot].push_back(u), G[u].push_back(tot);

                }

            }

            else low[u] = min(low[u], dfn[v]);

        }

}

int dep[MAXN<<1], sz[MAXN<<1], tp[MAXN<<1], son[MAXN<<1], fa[MAXN<<1];

void dfs1(int u, int ff) {

    dep[u] = dep[fa[u]=ff] + (sz[u] = 1);

    for(int i = G[u].size()-1, v; i >= 0; --i)

        if((v=G[u][i]) != ff) {

            dfs1(v, u), sz[u] += sz[v];

            if(sz[v] > sz[son[u]]) son[u] = v;

        }

}

void dfs2(int u, int Tp) {

    tp[u] = Tp;

    if(son[u]) dfs2(son[u], Tp);

    for(int i = G[u].size()-1, v; i >= 0; --i)

        if((v=G[u][i]) != fa[u] && v != son[u])

            dfs2(v, v);

}

inline int lca(int u, int v) {

    while(tp[u] != tp[v]) {

        if(dep[tp[u]] > dep[tp[v]]) u = fa[tp[u]];

        else v = fa[tp[v]];

    }

    return dep[u] < dep[v] ? u : v;

}

int f[MAXN<<1];

bool vis[MAXN<<1];

int dfs(int u) {

    if(vis[u]) return f[u]; vis[u] = 1;

    for(int i = G[u].size()-1, v; i >= 0; --i)

        if((v=G[u][i]) != fa[u])

            f[u] += dfs(v);

    return f[u];

}

int main() {

    rd(n), rd(m), rd(q); tot = n;

    for(int i = 1, u, v; i <= m; ++i) rd(u), rd(v), link(u, v);

    for(int i = 1; i <= n; ++i) if(!dfn[i]) tarjan(i, 0), --top;

    dfs1(1, 0), dfs2(1, 1);

    for(int i = 1, u, v, Lca; i <= q; ++i) {

        rd(u), rd(v);

        Lca = lca(u, v);

        ++f[u], ++f[v], --f[Lca], --f[fa[Lca]];

    }

    for(int i = 1; i <= n; ++i) printf("%d\n", dfs(i));

}
附上圆方树学习链接：

租酥雨的博客

 YoungNeal的博客
圆方树

BZOJ3331 压力（圆方树+树上差分）

题意

题解

CODE
