Hellc

「题目描述」

给定一棵树，树中有一些关键点，每次询问 任取一点出发 **经过所有关键点 **并回到起点的 最短路径长度。

要求支持以下修改：将一个点设为关键点，或者取消一个关键点。

点数 $n \leq 100000$ ，操作数 $m \leq 100000$ 。

「题目链接」

BZOJ 3991 寻宝游戏 「SDOI 2015」

「解题思路」

结论：

一种最优的走法是：将关键点按 DFS 序 排序，以第 1 个点为起点，依次走过所有点，然后回到起点。

证明：还有一些关节没想明白，留坑待补。

这样我们就可以计算答案了，为了支持插入和删除，我们需要动态维护 DFS 序，使用 set 即可。

插入点的时候，查找前趋和后继，从答案中删除前趋后继之间的贡献，然后加入前趋与新点、新点与后继的贡献即可。删除同理。

因为最后还要回到起点，可以把 set 看成环形的，写起来比较方便。

总结：只是关键点总数和点数同阶，但询问很多，不应往树形 DP 方向想；一般要考虑动态维护。

「AC 代码」

#include <cstdio>
#include <algorithm>
#include <set>

typedef long long int64;

const int MAX_N = 100000;
const int MAX_K = 17;

struct Node{
    struct Edge *e;

    int id, depth;
    int64 dist;
    Node *anc[MAX_K + 1];
    bool in;

    Node() : e(NULL), in(false) {}
} nodes[MAX_N];

inline Node* node(int i){
    return &nodes[i];
}

struct Edge{
    Node *to;
    Edge *next;
    int w;

    Edge() {}
    Edge(Node *fr, Node *to, int w) : to(to), next(fr->e), w(w) {}
} edges[2 * (MAX_N - 1)], *ptr = edges;

inline void link(Node *u, Node *v, int w){
    u->e = new (ptr++) Edge(u, v, w);
    v->e = new (ptr++) Edge(v, u, w);
}

Node *seq[MAX_N + 1];
inline void dfs(Node *v, Node *fa){
    static int dfsClock = 0;
    seq[v->id = ++dfsClock] = v;

    v->anc[0] = fa;
    for(int k = 1; k <= MAX_K; k++) v->anc[k] = v->anc[k - 1]->anc[k - 1];

    for(Edge *e = v->e; e; e = e->next) if(e->to != fa){
        e->to->depth = v->depth + 1;
        e->to->dist = v->dist + e->w;

        dfs(e->to, v);
    }
}

inline void dfs(Node *root){
    root->depth = 1, root->dist = 0;
    dfs(root, root);
}

inline Node* lca(Node *u, Node *v){
    if(u->depth < v->depth) std::swap(u, v);
    for(int k = MAX_K; ~k; --k) if(u->anc[k]->depth >= v->depth) u = u->anc[k];
    if(u == v) return u;
    for(int k = MAX_K; ~k; --k) if(u->anc[k] != v->anc[k]) u = u->anc[k], v = v->anc[k];
    return u->anc[0];
}

inline int64 dist(Node *u, Node *v){
    return u->dist + v->dist - 2 * lca(u, v)->dist;
}

struct Manager{
    typedef std::set<int>::const_iterator Iter;

    std::set<int> set;
    int64 ans;

    Manager() : ans(0) {}

    inline void findNeighbor(Iter it, Iter &pre, Iter &suc){
        Iter last = set.end();
        --last;

        if(it == set.begin()) pre = last; else --(pre = it);
        if(it == last) suc = set.begin(); else ++(suc = it);
    }

    inline void insert(Node *v){
        if(set.count(v->id)) return;

        Iter it = set.insert(v->id).first, pre, suc;
        findNeighbor(it, pre, suc);

        ans -= dist(seq[*pre], seq[*suc]);
        ans += dist(seq[*pre], seq[*it]);
        ans += dist(seq[*suc], seq[*it]);
    }

    inline void remove(Node *v){
        Iter it = set.find(v->id), pre, suc;
        findNeighbor(it, pre, suc);

        ans += dist(seq[*pre], seq[*suc]);
        ans -= dist(seq[*pre], seq[*it]);
        ans -= dist(seq[*suc], seq[*it]);

        set.erase(it);
    }

    inline void change(Node *v){
        v->in ^= 1;
        if(v->in) insert(v); else remove(v);
    }

    inline int64 getAns(){
        return ans;
    }
} *gm = new Manager();

int main(){
    int n, m;

    scanf("%d%d", &n, &m);
    for(int i = 0, u, v, w; i < n - 1; i++){
        scanf("%d%d%d", &u, &v, &w), u--, v--;

        link(node(u), node(v), w);
    }

    dfs(nodes);

    for(int i = 0, x; i < m; i++){
        scanf("%d", &x), x--;

        gm->change(node(x));
        printf("%lld\n", gm->getAns());
    }

    return 0;
}

就是这样啦～