CF1827E Bus Routes

设 u 能够通过不超过一条路径到达的点集为 S_u。

显然满足条件当且仅当 \forall u,v,S_u\bigcap S_v\neq\varnothing。

因为 S_u 是若干条经过 u 的路径的并，所以它是树上的一个连通块。

因此条件等价于 \bigcap S_u\neq\varnothing。

进一步地，等价于存在一个点 x 满足 \forall u,x\in S_u。

以 x 为根考虑，对于一个非叶子节点 u，取它子树内任意一个叶子 v。可以发现，如果 x\in S_v 那么一定有 x\in S_u，因此 x\in S_u 这个限制可以不用考虑。

我们可以依次考虑每个叶子 u，使用虚树+树上差分状物给 S_u 中的每一个点的点权增加 1。

如果存在某个点的点权等于叶子个数，那么它就是一个合法的 x，答案为 Yes。

否则答案为 No。此时还需要构造一组解。

这可以通过进一步分析解决，但是这里我们介绍一种简洁的做法。

定义一个叶子的子集 T 合法当且仅当 \forall u,v\in T,S_u\bigcap S_v\neq\varnothing。

直接沿用上面的做法，我们可以在 O(n) 的时间复杂度内询问任意一个 T 是否合法。

而我们可以设计一个只需要 O(\log n) 次询问的算法。

具体地，将所有叶子排成一个序列 a。先二分出最小的 r 使得 a_{1\dots r} 不合法，再二分出最大的 l 使得 a_{l\dots r} 不合法。

可以发现，S_{a_l}\bigcap S_{a_r}=\varnothing。因此我们在 O(n\log n) 的时间复杂度内找到了一组解。

总时间复杂度 O(n\log n)。

参考代码：

#include <bits/stdc++.h>
using namespace std;
#define N 500005
#define LIM 10000005
#define pb push_back
#define gc() (P1==P2 && (P2=(P1=buf)+fread(buf,1,LIM,stdin),P1==P2)?EOF:*P1++)
char buf[LIM],*P1=buf,*P2=buf;
int T,n,m,l,r,ps,lf[N],z[N],w[N],fa[N];vector<int> e[N],vc[N];
struct Node {int u,w;};vector<Node> vc1[N];
int dfsT;struct Point {int fa,dep,sz,hv,tp,dfn;}pt[N];
int rd()
{
    int res=0;char c=0;while(!isdigit(c)) c=gc();
    while(isdigit(c)) res=res*10+(c-48),c=gc();return res;
}
bool cmp(int x,int y) {return pt[x].dfn<pt[y].dfn;}
void dfs1(int u,int f)
{
    pt[u].fa=f;pt[u].dep=pt[f].dep+1;pt[u].sz=1;pt[u].hv=0;
    for(auto v:e[u]) if(v!=f)
    {dfs1(v,u);pt[u].sz+=pt[v].sz;if(pt[v].sz>pt[pt[u].hv].sz) pt[u].hv=v;}
}
void dfs2(int u,int f)
{
    pt[u].tp=f;pt[u].dfn=++dfsT;if(pt[u].hv) dfs2(pt[u].hv,f);
    for(auto v:e[u]) if(v!=pt[u].fa && v!=pt[u].hv) dfs2(v,v);
}
int LCA(int u,int v)
{
    while(pt[u].tp!=pt[v].tp)
    {if(pt[pt[u].tp].dep<pt[pt[v].tp].dep) swap(u,v);u=pt[pt[u].tp].fa;}
    if(pt[u].dep<pt[v].dep) swap(u,v);return v;
}
void build()
{
    vc1[lf[0]].clear();sort(z+1,z+z[0]+1,cmp);
    for(int i=1;i<=z[0];++i)
    {
        vc1[lf[0]].pb((Node) {pt[z[i]].dfn,1});
        if(i>1) vc1[lf[0]].pb((Node) {pt[LCA(z[i],z[i-1])].dfn,-1});
    }vc1[lf[0]].pb((Node) {pt[pt[LCA(z[1],z[z[0]])].fa].dfn,-1});
}
bool chk(int l,int r)
{
    fill(w,w+n+1,0);for(int i=l;i<=r;++i) for(auto j:vc1[i]) w[j.u]+=j.w;
    for(int i=n;i;--i) {if(w[i]==r-l+1) return 1;w[fa[i]]+=w[i];}return 0;
}
void slv()
{
    n=rd();m=rd();dfsT=lf[0]=0;for(int i=1;i<=n;++i) e[i].clear(),vc[i].clear();
    for(int i=1,u,v;i<n;++i) u=rd(),v=rd(),e[u].pb(v),e[v].pb(u);
    for(int i=1,u,v;i<=m;++i) u=rd(),v=rd(),vc[u].pb(v),vc[v].pb(u);
    dfs1(1,0);dfs2(1,1);for(int i=1;i<=n;++i) fa[pt[i].dfn]=pt[pt[i].fa].dfn;
    for(int i=1;i<=n;++i) if(e[i].size()==1)
    {z[0]=0;lf[++lf[0]]=z[++z[0]]=i;for(auto j:vc[i]) z[++z[0]]=j;build();}
    if(chk(1,lf[0])) {printf("Yes\n");return;}printf("No\n");l=1;r=lf[0];
    while(l<=r) {int mid=(l+r)/2;if(chk(1,mid)) l=mid+1;else r=mid-1;}
    ps=l;l=1;r=ps;
    while(l<=r) {int mid=(l+r)/2;if(chk(mid,ps)) r=mid-1;else l=mid+1;}
    printf("%d %d\n",lf[r],lf[ps]);
}
int main() {T=rd();while(T--) slv();return 0;}