本文共 1053 字，大约阅读时间需要 3 分钟。

Bugzilla由N个基地组成，这些基地通过N-1段双向地道连接成一棵树。RC需要尽可能多地搜索地道，而每次搜索都会炸毁当前基地。为了避免被困在地道中，RC必须确保每个基地的度数不超过2。

解决方案是通过剪枝树中的边，使得每个节点的度数最多为2。每当一个节点的度数大于2时，剪断连接到它的某条边。剪断的边数即为RC能搜索的地道数目。

具体步骤如下：

代码实现：

#include 
   
    #include 
    
     #include 
     
      using namespace std;int n, s, tot, b[100005], du[100005], head[100005];struct node { int to, next };void add(int x, int y) {    a[++tot] = { y, head[x] };    head[x] = tot;}void dp(int x, int father) {    b[x] = 1;    if (du[x] == 1 && a[head[x]].to == father) return;    for (int i = head[x]; i; i = a[i].next) {        int y = a[i].to;        if (b[y]) continue;        dp(y, x);    }    if (du[x] > 2) {        s -= (du[x] - 2);        du[father]--;    }}int main() {    scanf("%d", &n);    s = n - 1;    for (int i = 1; i <= n - 1; ++i) {        int x, y;        scanf("%d%d", &x, &y);        du[x]++;        du[y]++;        add(x, y);        add(y, x);    }    dp(1, 0);    cout << s << endl;}
     
    
   

这个方法确保了每个节点的度数不超过2，从而RC能搜索到最多的地道数目。