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

Problem Analysis

題目大意： 給定一棵具有節點按照進行編号的無向樹。給定條樹上路徑，要求求一個點集，能夠讓條路徑中每條路徑上至少有一點能夠出現在其中。要求最小化該點集。輸出最小點集的大小以及點集包含的點。(不要求輸出順序，答案不唯一)

思路分析：

由于要求點集最小化，是以需要貪心的選取點加入點集。

首先考慮不得不加的點：當給定的路徑隻包含一個點的時候，該點必須出現在點集中，因為無論被多少條路徑包含，它始終需要代表本身。對于非單點的路徑，我們将所有的路徑按照編号離線到一個鄰接表中，表的每個頭下标代表節點的編号，内部元素為目前節點所在的路徑編号序列。即：建立一個詢問集合，記錄每個端點所在的詢問編号。

然後一個樹上跑到葉節點，在回溯時對每兩個相鄰的點進行比較，我們采取貪心的政策，在相鄰集合中，以較小集合為基準，在較大集合中查詢是否與較小集合存在重疊元素。顯然當存在重疊元素的時候，目前點至少可以代表兩條以上的路徑，我們就将該點加入答案集合，同時清空該點。當元素不重疊時，順着回溯的順序将路徑編号上傳至父節點。

Accepted Code

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
vector<int> g[N], ans;
set<int> 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;
}