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 ;
}