2017-2018 Petrozavodsk Winter Training Camp, Saratov SU Contest C.Cover the Paths 贪心+DFS

题目大意： 给定一棵具有 n n n节点按照 1 … n 1 dots n 1…n进行编号的无向树。给定 m m m条树上路径，要求求一个点集，能够让 m m m条路径中每条路径上至少有一点能够出现在其中。要求最小化该点集。输出最小点集的大小以及点集包含的点。(不要求输出顺序，答案不唯一)

思路分析：

由于要求点集最小化，因此需要贪心的选取点加入点集。

首先考虑不得不加的点：当给定的路径只包含一个点的时候，该点必须出现在点集中，因为无论被多少条路径包含，它始终需要代表本身。对于非单点的路径，我们将所有的路径按照编号离线到一个邻接表中，表的每个头下标代表节点的编号，内部元素为当前节点所在的路径编号序列。即：建立一个询问集合，记录每个端点所在的询问编号。

然后一个树上 D F S DFS DFS跑到叶节点，在回溯时对每两个相邻的点进行比较，我们采取贪心的策略，在相邻集合中，以较小集合为基准，在较大集合中查询是否与较小集合存在重叠元素。显然当存在重叠元素的时候，当前点至少可以代表两条以上的路径，我们就将该点加入答案集合，同时清空该点。当元素不重叠时，顺着回溯的顺序将路径编号上传至父节点。

由于每个节点都会被遍历到一次，因此总复杂度 O ( n ) O(n) O(n)。

本题目也可以用 L C A LCA LCA等方式解决。但可能实现上上不如这样贪简单一些。

#include 
using namespace std;

const int N = 1e5 + 10;
vector g[N], ans;
set q[N];

int n, m;
int chose[N], flag[N], anscnt = 0;

void dfs(int u, int fa){
    for(auto v : g[u]){
        if(v != fa){
            dfs(v, u);
            if(q[u].size() < q[v].size()) swap(q[u], q[v]); 	//骚操作，直接交换
            for(auto t : q[v]){
                if(q[u].find(t) != q[u].end()) flag[u] = 1;
                else q[u].insert(t);
            }
        }
    }
    if(flag[u]) q[u].clear();
}

signed main(){
    cin >> n;
    for(int i = 1, u, v; i <= n - 1; i++){
        cin >> u >> v;
        g[u].push_back(v), g[v].push_back(u);
    }
    cin >> m;
    for(int i = 1, u, v; i <= m; i++){
        cin >> u >> v;
        if(u == v) flag[u] = 1;
        else q[u].insert(i), q[v].insert(i);
        
    }
    dfs(1, 0);
    for(int i = 0; i <= n; i++)
        if(flag[i]) ans.push_back(i);
    cout << ans.size() << endl;
    for(int i = 0; i < ans.size(); i++) cout << ans[i] << ((i == ans.size() - 1) ? 'n' : ' '); 
    return 0;
}