C语言-蓝桥杯2023年第十四届省赛真题-砍树

题目描述

给定一棵由 n 个结点组成的树以及 m 个不重复的无序数对 (a1, b1), (a2, b2),

. . . , (am, bm)，其中 ai?互不相同，bi?互不相同，ai?≠ bj(1 ≤ i, j ≤ m)。

小明想知道是否能够选择一条树上的边砍断，使得对于每个 (ai?, bi) 满足 ai和 bi?不连通，如果可以则输出应该断掉的边的编号（编号按输入顺序从 1 开始），否则输出 -1.

输入格式

输入共 n + m 行，第一行为两个正整数 n，m。

后面 n ? 1 行，每行两个正整数 xi，yi?表示第 i 条边的两个端点。

后面 m 行，每行两个正整数 ai，bi。

输出格式

一行一个整数，表示答案，如有多个答案，输出编号最大的一个。

样例输入

6 2 1 2 2 3 4 3 2 5 6 5 3 6 4 5 4

样例输出

4

提示

断开第 2 条边后形成两个连通块：{3, 4}，{1, 2, 5, 6}，满足 3 和 6 不连通，4 和 5 不连通。

断开第 4 条边后形成两个连通块：{1, 2, 3, 4}，{5, 6}，同样满足 3 和 6 不连通，4 和 5 不连通。

4 编号更大，因此答案为 4。

对于 30% 的数据，保证 1 < n ≤ 1000。

对于 100% 的数据，保证 1 < n ≤ 105，1 ≤ m ≤ 2/n。

解题：

#include <iostream>
#include <queue>
#include <map>
#include <set>
#include <stack>
#include <string>
#include<functional>
#include <math.h>
#include <algorithm>
#include<unordered_map>
#include<ctime>
#include <cstring>
#define lowbit(x) (-x) & x
#define ll long long
const int N = 3e6;
using namespace std;    
const int mod = 1e9 + 7;
ll __pow(ll x,ll y){
  ll res = 1;
  while(y){
      if(y&1)res = (res * x);
      y>>=1;
      x = (x * x);
  }
  return res;
}
ll cal(ll v1, ll v2){
  return v1*__pow(v2,mod-2)%mod;
}
ll C(ll x,ll y){
  ll res = 1;
  for(int i = 1,j = x + 1; j <= y;j++, i++){
      res*=j;
      res/=i;
  }
  return res;
}
ll gcd(ll x, ll y){
  if(y == 0)return x;
  else return gcd(y, x%y);
}
struct node{
  int to,nxt,c = 0,idx;
}e[N];
int cnt = 0;
int head[N];
void add(int u, int v){
  e[++cnt].nxt = head[u];
  e[cnt].to = v;
  head[u] = cnt;
  e[cnt].c = 0;
  e[cnt].idx = (cnt + 1)/2;
}
void solve(){   
  int n,m;
  cin>>n>>m;
  for(int i = 0; i < n - 1; ++i){
      int u,v;
      cin>>u>>v;
      u--,v--;
      add(u, v);
      add(v, u);
  }
  map<ll,int>lca;
  vector<int>query[n];
  for(int i = 0; i < m;++i){
      int u, v;
      cin>>u>>v;
      u--, v--;
      query[u].push_back(v);
      query[v].push_back(u);
  } 
  int p[n];
  int f[n];
  vector<int>diff(n, 0);
  vector<int>color(n, 0);
  for(int i = 0; i < n;++i)f[i] = i;
  function<int(int)>find = [&](int x)->int{return (f[x] == x)?x : f[x] = find(f[x]);};
  function<void(int,int)>tarjan = [&](int u,int fa){
      color[u] = 1;
      p[u] = fa;
      for(int i = head[u];i ; i = e[i].nxt){
          int v = e[i].to;
          if(color[v]==0){
              tarjan(v, u);
              f[v] = u;
          }
      }
      for(int v : query[u]){
          if(color[v]==2 || u == v){
              int ffa = find(v);
              diff[u]++;
              diff[v]++;
              lca[(ll)u*(1ll<<32) + v] = ffa;
              lca[(ll)v*(1ll<<32) + u] = ffa;
              diff[ffa]-=2;
          }
      }
      color[u] = 2;
  };
  tarjan(0, -1);
  int maxe = -1;
  function<void(int,int)>dfs = [&](int u, int fa){
      for(int i = head[u];i; i = e[i].nxt){
          int v = e[i].to;
          if(v == fa)continue;
          dfs(v, u);
          int id = e[i].idx;
          diff[u] += diff[v];    
          if(diff[v] == m){
              maxe = max(maxe, id);
          }
      }   
  };
  dfs(0, -1);
  cout<<maxe<<endl;
}   
int main(){ 
  ios::sync_with_stdio(false);
  cout.tie(0);
  cin.tie(0);
  int t;
  t = 1;
  while(t--){
      solve();
  }
  return 0 ;
}