互联网建设网站,深圳市网站制作公司,网站域名怎么用,怎么做产品推广平台题目描述
给定一棵由 n 个结点组成的树以及 m 个不重复的无序数对 (a1, b1), (a2, b2),
. . . , (am, bm)#xff0c;其中 ai 互不相同#xff0c;bi 互不相同#xff0c;ai ≠ bj(1 ≤ i, j ≤ m)。
小明想知道是否能够选择一条树上的边砍断#xff0c;使得对于每个 (a…题目描述
给定一棵由 n 个结点组成的树以及 m 个不重复的无序数对 (a1, b1), (a2, b2),
. . . , (am, bm)其中 ai 互不相同bi 互不相同ai ≠ bj(1 ≤ i, j ≤ m)。
小明想知道是否能够选择一条树上的边砍断使得对于每个 (ai , bi) 满足 ai和 bi 不连通如果可以则输出应该断掉的边的编号编号按输入顺序从 1 开始否则输出 -1.
输入格式
输入共 n m 行第一行为两个正整数 nm。
后面 n − 1 行每行两个正整数 xiyi 表示第 i 条边的两个端点。
后面 m 行每行两个正整数 aibi。
输出格式
一行一个整数表示答案如有多个答案输出编号最大的一个。
样例输入
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 ≤ 1051 ≤ m ≤ 2/n。
解题
#include iostream
#include queue
#include map
#include set
#include stack
#include string
#includefunctional
#include math.h
#include algorithm
#includeunordered_map
#includectime
#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(y1)res (res * x);y1;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;cinnm;for(int i 0; i n - 1; i){int u,v;cinuv;u--,v--;add(u, v);add(v, u);}mapll,intlca;vectorintquery[n];for(int i 0; i m;i){int u, v;cinuv;u--, v--;query[u].push_back(v);query[v].push_back(u);} int p[n];int f[n];vectorintdiff(n, 0);vectorintcolor(n, 0);for(int i 0; i n;i)f[i] i;functionint(int)find [](int x)-int{return (f[x] x)?x : f[x] find(f[x]);};functionvoid(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*(1ll32) v] ffa;lca[(ll)v*(1ll32) u] ffa;diff[ffa]-2;}}color[u] 2;};tarjan(0, -1);int maxe -1;functionvoid(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);coutmaxeendl;
}
int main(){ ios::sync_with_stdio(false);cout.tie(0);cin.tie(0);int t;t 1;while(t--){solve();}return 0 ;
}
