A. 暗的连锁
http://222.180.160.110:1024/contest/3470/problem/1
不难发现树上的边和附加边是两个独立的部分。
若只看所有附加边，对于某一条附加边，当它是这些附加边中的桥时，切断它所连接的两点在树上的简单路径即可达到目的。
于是我深陷于这个思路想了很久。最后 GM 告诉我们了一种新的思路：对于附加边，将 组成 它所连接的两点在树上的简单路径 的边 的权值统一加一，最后遍历每条树边：若未被标记过，则说明切掉这条边后，图已经分为两部分，答案加上附加边总数；若只被标记过一次，则贡献为标记它的那条附加边，即贡献为 1。
将边权下移至点权，则问题转化为树剖 / 树上差分。这里我用的是更难写的树剖（因为好久没写过了怕忘了）。
事实上也确实忘了。有一行判断完全写错了。紫菜！
namespace XSC062 {
#define lt (p << 1)
#define rt (lt | 1)
using namespace fastIO;
const int maxn = 1e5 + 5;
struct _ {
int u, d;
int l, r;
};
_ t[maxn << 2];
std::vector<int> g[maxn];
int n, m, x, y, now, res, ans;
int siz[maxn], son[maxn], fa[maxn];
int top[maxn], dfn[maxn], tab[maxn], dep[maxn];
inline void swap(int &x, int &y) {
x ^= y ^= x ^= y;
return;
}
inline void pushup(int p) {
t[p].u = t[lt].u + t[rt].u;
return;
}
inline void pushdown(int p) {
if (t[p].d) {
t[lt].d += t[p].d;
t[rt].d += t[p].d;
t[lt].u += (t[lt].r - t[lt].l + 1) * t[p].d;
t[rt].u += (t[rt].r - t[rt].l + 1) * t[p].d;
t[p].d = 0;
}
return;
}
void bld(int p, int l, int r) {
t[p].l = l, t[p].r = r;
if (l == r)
return;
int mid = (l + r) >> 1;
bld(lt, l, mid);
bld(rt, mid + 1, r);
return;
}
void upd(int p, int l, int r, int v) {
if (l <= t[p].l && t[p].r <= r) {
t[p].d += v;
t[p].u += (t[p].r - t[p].l + 1) * v;
return;
}
pushdown(p);
int mid = (t[p].l + t[p].r) >> 1;
if (l <= mid)
upd(lt, l, r, v);
if (r > mid)
upd(rt, l, r, v);
pushup(p);
return;
}
int qry(int p, int x) {
if (t[p].l == t[p].r)
return t[p].u;
pushdown(p);
int mid = (t[p].l + t[p].r) >> 1;
if (x <= mid)
return qry(lt, x);
return qry(rt, x);
}
void DFS1(int x, int f) {
siz[x] = 1, fa[x] = f;
for (auto i : g[x]) {
if (i == f)
continue;
dep[i] = dep[x] + 1;
DFS1(i, x);
siz[x] += siz[i];
if (siz[i] > siz[son[x]])
son[x] = i;
}
return;
}
void DFS2(int x, int t) {
top[x] = t;
dfn[x] = ++now;
tab[now] = x;
if (son[x])
DFS2(son[x], t);
for (auto i : g[x]) {
if (i == fa[x])
continue;
if (i != son[x])
DFS2(i, i);
}
return;
}
inline void upd(int x, int y, int v) {
while (top[x] != top[y]) {
if (dep[top[x]] < dep[top[y]])
swap(x, y);
upd(1, dfn[top[x]], dfn[x], v);
x = fa[top[x]];
}
if (dep[x] < dep[y])
swap(x, y);
upd(1, dfn[y], dfn[x], v);
upd(1, dfn[y], dfn[y], -v);
return;
}
inline void add(int x, int y) {
g[x].push_back(y);
return;
}
int main() {
read(n), read(m);
for (int i = 1; i < n; ++i) {
read(x), read(y);
add(x, y), add(y, x);
}
dep[1] = 1;
DFS1(1, -1), DFS2(1, 1);
bld(1, 1, n);
for (int i = 1; i <= m; ++i) {
read(x), read(y);
upd(x, y, 1);
}
for (int i = 2; i <= n; ++i) {
res = qry(1, dfn[i]);
if (res == 0)
ans += m;
else if (res == 1)
++ans;
}
print(ans);
return 0;
}
} // namespace XSC062