Solution

Tarjan 点双缩点， 加上树上差分计算。

注意特判。。。 我特判挂了好久呜呜呜

Code

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<vector>

 #define rd read()

 using namespace std;

 const int N = 1e5 + ;

 const int M = 2e5 + ;

 const int base = ;

 int head[N], tot;

 int Head[N << ], Tot;

 int low[N], dfn[N], cnt, col, c[N], cut[N], n, m, Q;

 int f[N << ][], nd, id[N], idf[N << ], dep[N << ];

 int st[N], tp, num[N], sum[N << ];

 vector<int> q[N << ];

 struct edge {

     int nxt, to;

 }e[M << ], E[M << ];

 int read() {

     int X = , p = ; char c = getchar();

     for (; c > '' || c < ''; c = getchar()) if (c == '-') p = -;

     for (; c >= '' && c <= ''; c = getchar()) X = X *  + c - '';

     return X * p;

 }

 void add(int u, int v) {

     e[++tot].to = v;

     e[tot].nxt = head[u];

     head[u] = tot;

 }

 void Add(int u, int v) {

     E[++Tot].to = v;

     E[Tot].nxt = Head[u];

     Head[u] = Tot;

 }

 void tarjan(int u) {

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

     st[++tp] = u;

     int flag = ;

     for (int i = head[u]; i; i = e[i].nxt) {

         int nt = e[i].to;

         if (!dfn[nt]) {

             tarjan(nt);

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

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

                 flag++;

                 if (flag >  || u - )

                     cut[u] = ;

                 col++;

                 for (; tp;) {

                     int v = st[tp--];

                     q[col].push_back(v);

                     if (v == nt)

                         break;

                 }

                 q[col].push_back(u);

             }

         }

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

     }

 }

 void dfs(int u) {

     for (int i = Head[u]; i; i = E[i].nxt) {

         int nt = E[i].to;

         if (f[u][] == nt)

             continue;

         f[nt][] = u;

         dep[nt] = dep[u] + ;

         dfs(nt);

     }

 }

 int LCA(int x, int y) {

     if (dep[x] < dep[y])

         swap(x, y);

     for (int k = base - ; ~k; --k)

         if (dep[f[x][k]] >= dep[y])

             x = f[x][k];

     if (x == y)

         return x;

     for (int k = base - ; ~k; --k)

         if (f[x][k] != f[y][k])

             x = f[x][k], y = f[y][k];

     return f[x][];

 }

 void dfs2(int u) {

     for (int i = Head[u]; i; i = E[i].nxt) {

         int nt = E[i].to;

         if (nt == f[u][])

             continue;

         dfs2(nt);

         sum[u] += sum[nt];

     }

     if(u > col)

         num[idf[u]] += sum[u];

 }

 int main()

 {

     //freopen("1.in","r", stdin);

     //freopen("out.out","w",stdout);

     n = rd; m = rd; Q = rd;

     for (int i = ; i <= m; ++i) {

         int u = rd, v = rd;

         add(u, v); add(v, u);

     }

     tarjan();

     nd = col;

     for (int i = ; i <= n; ++i)

         if (cut[i]) c[i] = ++nd, idf[nd] = i;

     for (int i = ; i <= col; ++i)

         for(int j = , len = q[i].size(); j < len; ++j) {

             int x = q[i][j];

             if (cut[x])

                 Add(i, c[x]), Add(c[x], i);

             else c[x] = i;

         }

     dep[] = ;

     dfs();

     for (int k = ; k < base; ++k)

         for (int i = ; i <= nd; ++i)

             f[i][k] = f[f[i][k - ]][k - ];

     for (; Q; Q--) {

         int u = rd, v = rd, lca;

         if (c[u] <= col) num[u]++;

         if (c[v] <= col) num[v]++;

         u = c[u]; v = c[v];

         if (u == v) continue;

         lca = LCA(u, v);

         sum[v]++; sum[u]++;

         sum[lca]--; sum[f[lca][]]--;

     }

     dfs2();

     for (int i = ; i <= n; ++i)

         printf("%d\n", num[i]);

 }

BZOJ 3331 [BeiJing2013]压力-Tarjan + 树上差分的相关教程结束。