# HDU 5296 Annoying problem（LCA模板+樹的dfs序心得） -开发者知识库

Problem Description Coco has a tree, whose nodes are conveniently labeled by 1,2,…,n, which has n-1 edge，each edge has a weight. An existing set S is initially empty.
Now there are two kinds of operation:

1 x： If the node x is not in the set S, add node x to the set S
2 x： If the node x is in the set S,delete node x from the set S

Now there is a annoying problem: In order to select a set of edges from tree after each operation which makes any two nodes in set S connected. What is the minimum of the sum of the selected edges’ weight ?

Input one integer number T is described in the first line represents the group number of testcases.( T<=10 )
For each test:
The first line has 2 integer number n,q(0<n,q<=100000) describe the number of nodes and the number of operations.
The following n-1 lines each line has 3 integer number u,v,w describe that between node u and node v has an edge weight w.(1<=u,v<=n,1<=w<=100)
The following q lines each line has 2 integer number x,y describe one operation.（x=1 or 2,1<=y<=n）

Output Each testcase outputs a line of "Case #x:" , x starts from 1.
The next q line represents the answer to each operation.

Sample Input
`16 51 2 21 5 25 6 22 4 22 3 21 51 31 41 22 5`

Sample Output
`Case #1:06884`

Author FZUACM
Source 2015 Multi-University Training Contest 1

d(a,b)min = dist[a] dist[b] - 2*dist[lca(a,b)],其中dist是節點到根節點的距離

`struct Node{    int u, v, w, next;};struct LCA{    int dp[2 * N][M];    bool vis[N];    int tot, head[N];    Node e[2*N];    void AddEdge (int u, int v, int w, int &k)    {        e[k].u = u, e[k].v = v, e[k].w = w;        e[k].next = head[u];        head[u] = k  ;    }    int ver[2 * N], d[2 * N], first[N], dis[N];//dis[i]表示節點i距離根節點的距離    //first[i]表示節點i的dfs序    //節點編號   深度  點編號位置  距離    void init()    {        mem(head,-1);        mem(vis,0);        tot = 0;dis[1] = 0;    }    void dfs (int u, int dep)    {        vis[u] = 1;        ver[  tot] = u;        first[u] = tot;        d[tot] = dep;        for (int k = head[u]; k != -1; k = e[k].next)        {            if (!vis[e[k].v])            {                int v = e[k].v, w = e[k].w;                dis[v] = dis[u]   w;                dfs (v, dep   1);                ver[  tot] = u;                d[tot] = dep;            }        }    }    void ST (int n)    {        for (int i = 1; i <= n;   i) dp[i][0] = i;        for (int j = 1; (1 << j) <= n;   j)        {            for (int i = 1; i   (1 << j) - 1 <= n;   i)            {                int a = dp[i][j - 1], b = dp[i   (1 << (j - 1) )][j - 1];                dp[i][j] = d[a] < d[b] ? a : b;            }        }    }    int RMQ (int l, int r)    {        int k = 0;        while ( (1 << (k   1) ) <= r - l   1) k  ;        int a = dp[l][k], b = dp[r - (1 << k)   1][k];        return d[a] < d[b] ? a : b;    }    int Lca(int u, int v)    {        int x = first[u], y = first[v];        if (x > y) swap (x, y);        return ver[RMQ (x, y)];    }}ans;`

ver表示遍歷過程中第i次訪問的點的編號，d表示遍歷過程中第i次訪問的點的深度

dfs序能把非線性的樹結構用線性結構保存下來，另外，dfs序一個很重要的性質是：

dfs序在樹狀結構中有很多用法，LCA只是其中一種（文尾貼了dfs序應用的相關資料）

LCA模板沒什么好說的，計算的部分代碼中說的很清楚了，上代碼：

`#define mem(a,x) memset(a,x,sizeof(a))#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<queue>#include<set>#include<stack>#include<cmath>#include<map>#include<stdlib.h>#include<cctype>#include<string>using namespace std;typedef long long ll;const int N = 400010;const int M = 45;struct Node{    int u, v, w, next;};struct LCA{    int dp[2 * N][M];    bool vis[N];    int tot, head[N];    Node e[2*N];    void AddEdge (int u, int v, int w, int &k)    {        e[k].u = u, e[k].v = v, e[k].w = w;        e[k].next = head[u];        head[u] = k  ;    }    //節點編號   深度  點編號位置  距離    int ver[2 * N], d[2 * N], first[N], dis[N];//dis[i]表示節點i距離根節點的距離    //first[i]表示節點i的dfs序    int p[2*N];//p[i]表示dfs序為i的節點    //即 ： 若 first[i] = j,則 p[j] = i    void init()    {        mem(head,-1);        mem(vis,0);        tot = 0;dis[1] = 0;    }    void dfs (int u, int dep)    {        vis[u] = 1;        ver[  tot] = u;        first[u] = tot;        p[tot] = u;        d[tot] = dep;        for (int k = head[u]; k != -1; k = e[k].next)        {            if (!vis[e[k].v])            {                int v = e[k].v, w = e[k].w;                dis[v] = dis[u]   w;                dfs (v, dep   1);                ver[  tot] = u;                d[tot] = dep;            }        }    }    void ST (int n)    {        for (int i = 1; i <= n;   i) dp[i][0] = i;        for (int j = 1; (1 << j) <= n;   j)        {            for (int i = 1; i   (1 << j) - 1 <= n;   i)            {                int a = dp[i][j - 1], b = dp[i   (1 << (j - 1) )][j - 1];                dp[i][j] = d[a] < d[b] ? a : b;            }        }    }    int RMQ (int l, int r)    {        int k = 0;        while ( (1 << (k   1) ) <= r - l   1) k  ;        int a = dp[l][k], b = dp[r - (1 << k)   1][k];        return d[a] < d[b] ? a : b;    }    int Lca(int u, int v)    {        int x = first[u], y = first[v];        if (x > y) swap (x, y);        return ver[RMQ (x, y)];    }}ans;set<int>s;bool vis[N 5];//判斷點是否在集合中int Cal(int u)//計算dfs序為u的點的加入集合增加的花費{    if (s.empty()) return 0;    int x,y;//x,y分別是比dfs序為u的點大的最小點和比它小的最大點    set<int>::iterator it = s.upper_bound(u);//返回集合中第一個鍵值大於u的元素迭代器位置    if (it == s.end()||it == s.begin())//沒有比他大的或者都比他大    {        x = ans.p[*s.rbegin()];//*s.rbegin()是dfs序,在這里轉換成了原樹上的節點保存於x        y = ans.p[*s.begin()];    }    else    {        x = ans.p[*it];        it--;        y = ans.p[*it];    }    u = ans.p[u];//u也換回成原樹上的節點來計算    return ans.dis[u] - ans.dis[ans.Lca(x,u)] - ans.dis[ans.Lca(y,u)]   ans.dis[ans.Lca(x,y)];}int main(){    int T;scanf("%d",&T);int kas = 0;    while (T--)    {        int n,m;scanf("%d %d",&n,&m);        s.clear();        ans.init();int k = 0;        for (int i = 1,u,v,w;i < n;  i)        {            scanf("%d %d %d",&u,&v,&w);            ans.AddEdge(u,v,w,k);            swap(u,v);            ans.AddEdge(u,v,w,k);        }        ans.dfs(1,1);        ans.ST(2*n-1);int op,u;        printf("Case #%d:\n",  kas);        int sun = 0;mem(vis,0);        for (int i = 0;i < m;  i)        {            scanf("%d %d",&op,&u);            if (op == 1)            {                if (!vis[u])                {                    vis[u] = 1;                    sun  = Cal(ans.first[u]);//用u的dfs序去計算                    s.insert(ans.first[u]);                }            }            else            {                if (vis[u])                {                    vis[u] = 0;                    s.erase(ans.first[u]);                    sun -= Cal(ans.first[u]);                }            }            printf("%d\n",sun);        }    }    return 0;}`

0条回复