题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5452
题意：给你一个图和它的生成树，要你在树上删一条边，问你最少删多少条边使得图不联通（开始时图一定联通）
解：
对每一条非树边对它两点之间的树上链的边+1，答案就是树上边的最小边权+1。处理上开始用了树状数组=TLE，其实由于只查询一次，用数组维护一下就好
/*
* Problem:
* Author: SHJWUDP
* Created Time: 2015/9/23 星期三 19:32:28
* File Name: 1001.cpp
* State:
* Memo:
*/
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm> using namespace std; struct Graph {
struct Edge {
int u, v;
};
int n, m;
vector<Edge> edges;
vector<vector<int>> G;
Graph(int _n):n(_n), G(_n){}
void addEdge(int u, int v) {
edges.push_back({u, v});
m=edges.size();
G[u].push_back(m-);
}
vector<int>& operator[](int x) {
return G[x];
}
}; struct LinkCutTree {
Graph G;
vector<int> fa, siz, son, dep, top;
vector<int> w;
int id;
vector<int> ans;
LinkCutTree(int n):G(n){}
void init() {
fa.resize(G.n);
siz.resize(G.n);
son.resize(G.n);
dep.resize(G.n);
top.resize(G.n);
w.resize(G.n);
id=; int root=;
fa[root]=-;
dfs1(root, );
dfs2(root, root);
ans.assign(G.n+, );
}
int dfs1(int u, int d) {
siz[u]=; dep[u]=d; son[u]=-;
for(auto i : G[u]) {
const auto& e=G.edges[i];
if(e.v==fa[u]) continue;
fa[e.v]=u;
siz[u]+=dfs1(e.v, d+);
if(son[u]==- || siz[son[u]]<siz[e.v]) son[u]=e.v;
}
return siz[u];
}
void dfs2(int u, int tp) {
w[u]=id++; top[u]=tp;
if(son[u]!=-) dfs2(son[u], tp);
for(auto i : G[u]) {
const auto & e=G.edges[i];
if(e.v==fa[u] || e.v==son[u]) continue;
dfs2(e.v, e.v);
}
}
void update(int u, int v) {
int f1=top[u], f2=top[v];
while(f1!=f2) {
if(dep[f1]<dep[f2]) swap(f1, f2), swap(u, v);
// cout<<"\tup: "<<w[f1]<<"\t"<<w[u]+1<<endl;
++ans[w[f1]]; --ans[w[u]+];
u=fa[f1]; f1=top[u];
}
if(u==v) return;
if(dep[u]>dep[v]) swap(u, v);
// cout<<"\tup: "<<w[u]<<"\t"<<w[v]<<endl;
++ans[w[son[u]]]; --ans[w[v]+];
}
}; int n, m;
int main() {
#ifndef ONLINE_JUDGE
freopen("in", "r", stdin);
//freopen("out", "w", stdout);
#endif
int T, now=;
scanf("%d", &T);
while(T--) {
scanf("%d%d", &n, &m);
LinkCutTree lct(n+);
Graph & G=lct.G;
for(int i=; i<n-; ++i) {
int a, b;
scanf("%d%d", &a, &b);
G.addEdge(a, b);
G.addEdge(b, a);
}
lct.init();
for(int i=n-; i<m; ++i) {
int a, b;
scanf("%d%d", &a, &b);
lct.update(a, b);
}
int ans=0x7f7f7f7f;
for(int i=; i<n; ++i) {
lct.ans[i]+=lct.ans[i-];
ans=min(ans, lct.ans[i]);
}
printf("Case #%d: %d\n", ++now, ans+);
}
return ;
}