C

简要题意

给定一棵n个点的树，再给定m对点，每对点表示一条路径。求一个最小点集，使得每条路径上都存在点集中的点。

数据范围

\(1\leq n,m\leq 10^5\)

简要题解

据说树上路径问题常常和LCA有关，于是我们对于每一条路径，考虑它的LCA。
对于LCA最深的那一条路径，一定把LCA放入点集是最优的。因为该路径上必须有一个点在点集内。
如果该路径与其他路径无交，那么取LCA肯定没问题。如果该路径与其他路径有交，那么LCA一定是交点之一，因为当前路径的LCA最深，而其他路径想要与当前路径有交，必须经过LCA才能下来。
那么就有一个贪心策略了：我们优先考虑LCA最深的路径，若该路径未被标记，则将LCA加入点集，并把经过LCA的所有路径标记。
具体实现的话，对于树上的每个点，我们维护一个set。对于每一条路径，我们将路径的标号扔进路径端点的set中，表示该路径未被标记。
然后我们Dfs，对于当前点，先遍历子树，然后将子树的set和当前点的set合并。如果合并过程中出现了重复元素，说明当前点是该元素对应路径的LCA，且该路径未被标记，那么我们就把这个点放入点集，然后清空该点的set，表示当前所有路径都被标记。
为了保证复杂度，合并过程采用启发式合并。
时间复杂度\(O(nlogn)\)
代码如下：

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+10;
struct EDGE{   int u,v,Next;   }Edge[MAXN<<1];
int n,m,Es,Ans;
int First[MAXN],Bel[MAXN],Have[MAXN];
set<int>Set[MAXN];
int Read()
{   int a=0,c=1;   char b=getchar();
    while(b!='-'&&(b<'0'||b>'9')) b=getchar();
    if(b=='-') c=-1,b=getchar();
    while(b>='0'&&b<='9') a=a*10+b-48,b=getchar();
    return a*c;
}
void Link(int u,int v){   Edge[++Es]=(EDGE){u,v,First[u]},First[u]=Es;   }
int Merge(int A,int B)
{   if(Set[A].size()<Set[B].size()) swap(A,B);
    for(int Ele:Set[B])
        if(Set[A].find(Ele)!=Set[A].end()) return Set[A].clear(),Set[B].clear(),-1;
        else Set[A].insert(Ele);
    return A;
}
int Dfs(int Now,int Ba)
{   //printf("Now=%d Ba=%d\n",Now,Ba);
    for(int i=First[Now],v;i!=-1;i=Edge[i].Next)
        if((v=Edge[i].v)!=Ba) Dfs(v,Now);
    if(Have[Now]) return Set[Bel[Now]].clear(),Ans++;
    for(int i=First[Now],v,New;i!=-1&&!Have[Now];i=Edge[i].Next)
    {   if((v=Edge[i].v)==Ba) continue ;
        if((New=Merge(Bel[Now],Bel[v]))==-1) Have[Now]=1,Ans++;
        else Bel[Now]=New;
    }
    //printf("Finish %d\n",Now);
}
int main()
{   n=Read(),memset(First,-1,sizeof(First));
    for(int i=1,u,v;i<n;i++) u=Read(),v=Read(),Link(u,v),Link(v,u);
    m=Read();
    for(int i=1,A,B;i<=m;i++) A=Read(),B=Read(),A==B?Have[A]=1:(Set[A].insert(i),Set[B].insert(i),0);
    for(int i=1;i<=n;i++) Bel[i]=i;
    Dfs(1,1),printf("%d\n",Ans);
    for(int i=1;i<=n;i++) Have[i]?printf("%d ",i):0;
}