$\quad$树上边差分
$\quad$对于每一组数对$a_{i},b_{i}$,我们可以假设成每次都对$(u,v)$之间的简单路径进行权值$+ 1$操作,那么如果可以完全分离两个集合,就等价于我们可以找到这样一条边,该边权在经过若干次操作后,边权为$m$。
$\quad$对于每一组数对,我们可以用树上边差分来实现对边的加权操作。
$\quad$在每次某一棵子树计算完毕后,就等价于从当前节点到该子树的根节点的这一条边的所有操作后的加权被计算完,因此该条边的权值即为该子树$j$,的树上前缀。
AC Code:
#include<bits/stdc++.h>
#pragma optimize(2)
#define endl '\n'
#define ll() to_ullong()
#define string() to_string()
#define Endl endl
using namespace std;
typedef long long ll;
typedef pair<int,int>PII;
typedef unsigned long long ull;
const int M=2010;
const int P=13331;
const ll llinf=0x3f3f3f3f3f3f3f3f;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
const int N=2e6+10;
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};
int n,m;
int e[N],ne[N],h[N],idx;
void add(int a,int b)
{
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
int dep[N],fa[N][32];
map<PII,int>mp;
int id;
void dfs1(int u,int father,int depth)
{
dep[u]=depth+1,fa[u][0]=father;
for(int k=1;k<=20;k++)fa[u][k]=fa[fa[u][k-1]][k-1];
for(int i=h[u];~i;i=ne[i])
{
int j=e[i];
if(j!=father)dfs1(j,u,depth+1);
}
}
int lca(int x,int y)
{
if(dep[x]<dep[y])swap(x,y);
for(int k=20;k>=0;k--)
if(dep[fa[x][k]]>=dep[y])x=fa[x][k];
if(x==y)return x;
for(int k=20;k>=0;k--)
if(fa[x][k]!=fa[y][k])x=fa[x][k],y=fa[y][k];
return fa[x][0];
}
int ans,sum[N];
int dfs2(int u,int father)
{
for(int i=h[u];~i;i=ne[i])
{
int j=e[i];
if(j!=father)
{
sum[u]+=dfs2(j,u);
if(sum[j]==m)ans=max(ans,mp[{u,j}]);
}
}
return sum[u];
}
void solve()
{
memset(h,-1,sizeof h);
cin>>n>>m;
for(int i=1;i<n;i++)
{
int a,b;cin>>a>>b;
add(a,b),add(b,a);
mp[{a,b}]=mp[{b,a}]=i;
}
dfs1(1,0,1);
for(int i=1;i<=m;i++)
{
int a,b;cin>>a>>b;
if(dep[a]>dep[b])swap(a,b);
int anc=lca(a,b);
if(anc==a)sum[a]--,sum[b]++;
else
{
sum[a]++,sum[b]++;
sum[anc]-=2;
}
}
//
//O(len-1)
dfs2(1,0);
if(!ans)cout<<"-1"<<endl;
else cout<<ans<<endl;
return ;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
#ifndef ONLINE_JUDGE
freopen("test.in", "r", stdin);
#endif
solve();
return 0;
}