数据结构 – hahaschool

树状数组(BIT)实现

September 02, 20152015-09-02hahaschoolLeave a comment

在这里只提供模板。

一维情形

提供区间和功能，支援单点delta更新。sum得到的是[1,pos]的值的和。

#pragma mark - Binary Indexed Tree (BIT) 1D
//index begins from ONE
//init:memset BIT,set BIT_size
int BIT[MAXN];//container,may need to adjust MAXN or type.assuming the index won't overflow int
int BIT_size;//should assign when use

inline int lowbit(int a){
    return a & (-a);
}

void BIT_modify(int pos,int delta){//type of delta may need to modify
    for (int x = pos; x <= BIT_size; x += lowbit(x)) {
        BIT[x] += delta;
    }
}

int BIT_sum(int pos){//return type may alter
    int ret = 0;
    for (int x = pos; x > 0; x -= lowbit(x)) {
        ret += BIT[x];
    }
    return ret;
}
#pragma mark -

#pragma mark - Binary Indexed Tree (BIT) 1D

//index begins from ONE

//init:memset BIT,set BIT_size

int BIT[MAXN];//container,may need to adjust MAXN or type.assuming the index won't overflow int

int BIT_size;//should assign when use

inline int lowbit(int a){

return a & (-a);

}

void BIT_modify(int pos,int delta){//type of delta may need to modify

for (int x = pos; x <= BIT_size; x += lowbit(x)) {

BIT[x] += delta;

}

int BIT_sum(int pos){//return type may alter

int ret = 0;

for (int x = pos; x > 0; x -= lowbit(x)) {

ret += BIT[x];

}

return ret;

}

#pragma mark -

二维情形

提供矩阵和功能，支援单点更新，sum得到的是从(1,1)拉到(posi,posj)的矩阵中数的总和。

#pragma mark - Binary Indexed Tree (BIT) 2D
//index begins from ONE
//init:memset BIT,set BIT_size
int BIT[MAXR][MAXC];//container,may need to adjust MAXN or type.assuming the index won't overflow int
int BIT_Rsize;//number of rows
int BIT_Csize[MAXC];//number of columns

inline int lowbit(int a){
    return a & (-a);
}

void BIT_modify(int posi,int posj,int delta){//type of delta may need to modify
    for (int x = posi; x <= BIT_Rsize; x += lowbit(x)) {
        for (int y = posj; y <= BIT_Csize[y]; y += lowbit(y)) {
            BIT[x][y] += delta;
        }
    }
}

int BIT_sum(int posi,int posj){//return type may alter
    int ret = 0;
    for (int x = posi; x > 0; x -= lowbit(x)) {
        for (int y = posj; y > 0; y -= lowbit(x)) {
            ret += BIT[x][y];
        }
    }
    return ret;
}
#pragma mark -

#pragma mark - Binary Indexed Tree (BIT) 2D

//index begins from ONE

//init:memset BIT,set BIT_size

int BIT[MAXR][MAXC];//container,may need to adjust MAXN or type.assuming the index won't overflow int

int BIT_Rsize;//number of rows

int BIT_Csize[MAXC];//number of columns

inline int lowbit(int a){

return a & (-a);

}

void BIT_modify(int posi,int posj,int delta){//type of delta may need to modify

for (int x = posi; x <= BIT_Rsize; x += lowbit(x)) {

for (int y = posj; y <= BIT_Csize[y]; y += lowbit(y)) {

BIT[x][y] += delta;

}

int BIT_sum(int posi,int posj){//return type may alter

int ret = 0;

for (int x = posi; x > 0; x -= lowbit(x)) {

for (int y = posj; y > 0; y -= lowbit(x)) {

ret += BIT[x][y];

}

return ret;

}

#pragma mark -

SPOJ LCS Longest Common Substring

August 09, 20152015-08-09hahaschool2 Comments

［等待填坑］

//
//  SPOJ LCS.cpp
//  playground
//
//  Created by Adam Chang on 2015/08/08.
//  Copyright © 2015年 Adam Chang. All rights reserved.
//

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <cmath>
#include <set>
#include <stack>
#include <cmath>
#include <map>

using namespace std;

struct SAM_State{
    int mxn;
    SAM_State *to[26];
    SAM_State *parent;
    SAM_State(int _mxn){
        mxn = _mxn;
        memset(to, 0, sizeof(to));
        parent = NULL;
    }
};

SAM_State* SAM_Append(SAM_State *last,SAM_State *root,int ch){
    SAM_State *p = last;
    SAM_State *np = new SAM_State(p -> mxn + 1);
    while (p && p -> to[ch] == NULL) {
        p -> to[ch] = np;
        p = p -> parent;
    }
    if (p != NULL) {
        SAM_State *q = p -> to[ch];
        if (q -> mxn == p -> mxn + 1) {
            np -> parent = q;
        }else{
            SAM_State *nq = new SAM_State(p -> mxn + 1);
            nq -> parent = q -> parent;
            q -> parent = nq;
            np -> parent = nq;
            memcpy(nq -> to, q -> to, sizeof(q -> to));
            while (p && p -> to[ch] == q) {
                p -> to[ch] = nq;
                p = p -> parent;
            }
        }
    }else{
        np -> parent = root;
    }
    last = np;
    return last;
}

SAM_State* SAM_Build(string str){
    SAM_State *root = new SAM_State(0);
    SAM_State *last = root;
    for (int i = 0; i < str.size(); i++) {
        last = SAM_Append(last, root, str[i] - 'a');
    }
    return root;
}


int main(){
    string a,b;
    cin >> a >> b;
    SAM_State *sam_root = SAM_Build(a);
    SAM_State *sam = sam_root;
    int ans = 0;
    int curcnt = 0;
    for (int i = 0; i < b.size(); i++) {
        if (sam -> to[b[i]-'a'] != NULL) {
            curcnt++;
            sam = sam -> to[b[i]-'a'];
        }else{
            ans = max(curcnt,ans);
            curcnt = 0;
            while (sam -> parent) {
                sam = sam -> parent;
                if (sam -> to[b[i]-'a'] != NULL) {
                    curcnt = sam->mxn+1;
                    sam = sam -> to[b[i]-'a'];
                    break;
                }
            }
        }
    }
    cout << max(curcnt,ans) << endl;
    return 0;
}

100

101

102

103

// SPOJ LCS.cpp

// playground

// Created by Adam Chang on 2015/08/08.

#include <iostream>

#include <algorithm>

#include <queue>

#include <vector>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <iomanip>

#include <cmath>

#include <set>

#include <stack>

#include <cmath>

#include <map>

using namespace std;

struct SAM_State{

int mxn;

SAM_State *to[26];

SAM_State *parent;

SAM_State(int _mxn){

mxn = _mxn;

memset(to, 0, sizeof(to));

parent = NULL;

}

};

SAM_State* SAM_Append(SAM_State *last,SAM_State *root,int ch){

SAM_State *p = last;

SAM_State *np = new SAM_State(p -> mxn + 1);

while (p && p -> to[ch] == NULL) {

p -> to[ch] = np;

p = p -> parent;

}

if (p != NULL) {

SAM_State *q = p -> to[ch];

if (q -> mxn == p -> mxn + 1) {

np -> parent = q;

}else{

SAM_State *nq = new SAM_State(p -> mxn + 1);

nq -> parent = q -> parent;

q -> parent = nq;

np -> parent = nq;

memcpy(nq -> to, q -> to, sizeof(q -> to));

while (p && p -> to[ch] == q) {

p -> to[ch] = nq;

p = p -> parent;

}

}else{

np -> parent = root;

}

last = np;

return last;

}

SAM_State* SAM_Build(string str){

SAM_State *root = new SAM_State(0);

SAM_State *last = root;

for (int i = 0; i < str.size(); i++) {

last = SAM_Append(last, root, str[i] - 'a');

}

return root;

}

int main(){

string a,b;

cin >> a >> b;

SAM_State *sam_root = SAM_Build(a);

SAM_State *sam = sam_root;

int ans = 0;

int curcnt = 0;

for (int i = 0; i < b.size(); i++) {

if (sam -> to[b[i]-'a'] != NULL) {

curcnt++;

sam = sam -> to[b[i]-'a'];

}else{

ans = max(curcnt,ans);

curcnt = 0;

while (sam -> parent) {

sam = sam -> parent;

if (sam -> to[b[i]-'a'] != NULL) {

curcnt = sam->mxn+1;

sam = sam -> to[b[i]-'a'];

break;

}

cout << max(curcnt,ans) << endl;

return 0;

}

SPOJ LCS2 Longest Common Substring II

August 09, 20152015-08-09hahaschoolLeave a comment

［详细题解等待填坑］

SPOJ真是业界奇葩

//
//  SPOJ LCS2.cpp
//  playground
//
//  Created by Adam Chang on 2015/08/08.
//  Copyright © 2015年 Adam Chang. All rights reserved.
//

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <cmath>
#include <set>
#include <stack>
#include <cmath>
#include <map>

using namespace std;

struct SAM_State{
    int mxn;
    int mi;
    int mx;
    SAM_State *to[26];
    SAM_State *parent;
    void init(int _mxn){
        mxn = _mxn;
        memset(to, NULL, sizeof(to));
        parent = NULL;
        mx = 0;
        mi = 909303;
    }
} idx[200005];

int totalNode = 0;
int mxmxn = 0;
SAM_State *idx_sorted[200005];

SAM_State* SAM_Append(SAM_State *last,SAM_State *root,int ch){
    SAM_State *p = last;
    SAM_State *np = &idx[++totalNode];
    np -> mxn = p -> mxn + 1;
    mxmxn = max(mxmxn, np -> mxn);
    while (p && p -> to[ch] == NULL) {
        p -> to[ch] = np;
        p = p -> parent;
    }
    if (p != NULL) {
        SAM_State *q = p -> to[ch];
        if (q -> mxn == p -> mxn + 1) {
            np -> parent = q;
        }else{
            SAM_State *nq = &idx[++totalNode];
            *nq = *q;
            nq -> mxn = p -> mxn + 1;
            q -> parent = nq;
            np -> parent = nq;
            while (p && p -> to[ch] == q) {
                p -> to[ch] = nq;
                p = p -> parent;
            }
        }
    }else{
        np -> parent = root;
    }
    last = np;
    return last;
}

void init(int n){
    for (int i = 0; i <= n ; i++) {
        idx[i].init(0);
    }
    totalNode = 0;
    mxmxn = 0;
}

SAM_State* SAM_Build(char* str){
    int len = (int)strlen(str);
    init(2*len);
    SAM_State *root = &idx[0];
    SAM_State *last = root;
    for (int i = 0; i < len; i++) {
        last = SAM_Append(last, root, str[i] - 'a');
    }
    return root;
}

int cnt[100005];
void toposort(){
    memset(cnt, 0, sizeof(cnt));
    for (int i = 0; i <= totalNode; i++) {
        cnt[idx[i].mxn]++;
    }
    for (int i = 1; i <= mxmxn; i++) {
        cnt[i] += cnt[i-1];
    }
    for (int i = 0; i <= totalNode; i++) {
        idx_sorted[--cnt[idx[i].mxn]] = &idx[i];
    }
}



char a[100005];

int main(){
    scanf("%s",a);
    SAM_State *sam_root = SAM_Build(a);
    toposort();
    while (scanf("%s",a) != EOF) {
        int len = (int)strlen(a);
        SAM_State *sam = sam_root;
        int tmp = 0;
        for (int i = 0; i < len; i++) {
            if (sam -> to[a[i] - 'a'] != NULL) {
                tmp++;
                sam = sam -> to[a[i] - 'a'];
            }else{
                while (sam && sam -> to[a[i] - 'a'] == NULL) {
                    sam = sam -> parent;
                }
                if (sam == NULL) {
                    sam = sam_root;
                    tmp = 0;
                }else{
                    tmp = sam -> mxn + 1;
                    sam = sam -> to[a[i] - 'a'];
                }
            }
            sam -> mx = max(sam -> mx, tmp);
        }
        for (int j = totalNode; j >= 0; j--) {
            SAM_State *cur = idx_sorted[j];
            cur -> mi = min(cur -> mi, cur -> mx);
            if (cur -> parent != NULL) {
                cur -> parent -> mx = max(cur -> parent -> mx, cur -> mx);
                cur -> parent -> mx = min(cur -> parent -> mxn,cur -> parent -> mx);
            }
            cur -> mx = 0;
        }
    }
    int res = 0;
    for (int i = 0; i <= totalNode; i++) {
        res = max(idx[i].mi, res);
    }
    printf("%d\n",res);
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

// SPOJ LCS2.cpp

// playground

// Created by Adam Chang on 2015/08/08.

#include <iostream>

#include <algorithm>

#include <queue>

#include <vector>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <iomanip>

#include <cmath>

#include <set>

#include <stack>

#include <cmath>

#include <map>

using namespace std;

struct SAM_State{

int mxn;

int mi;

int mx;

SAM_State *to[26];

SAM_State *parent;

void init(int _mxn){

mxn = _mxn;

memset(to, NULL, sizeof(to));

parent = NULL;

mx = 0;

mi = 909303;

}

} idx[200005];

int totalNode = 0;

int mxmxn = 0;

SAM_State *idx_sorted[200005];

SAM_State* SAM_Append(SAM_State *last,SAM_State *root,int ch){

SAM_State *p = last;

SAM_State *np = &idx[++totalNode];

np -> mxn = p -> mxn + 1;

mxmxn = max(mxmxn, np -> mxn);

while (p && p -> to[ch] == NULL) {

p -> to[ch] = np;

p = p -> parent;

}

if (p != NULL) {

SAM_State *q = p -> to[ch];

if (q -> mxn == p -> mxn + 1) {

np -> parent = q;

}else{

SAM_State *nq = &idx[++totalNode];

*nq = *q;

nq -> mxn = p -> mxn + 1;

q -> parent = nq;

np -> parent = nq;

while (p && p -> to[ch] == q) {

p -> to[ch] = nq;

p = p -> parent;

}

}else{

np -> parent = root;

}

last = np;

return last;

}

void init(int n){

for (int i = 0; i <= n ; i++) {

idx[i].init(0);

}

totalNode = 0;

mxmxn = 0;

}

SAM_State* SAM_Build(char* str){

int len = (int)strlen(str);

init(2*len);

SAM_State *root = &idx[0];

SAM_State *last = root;

for (int i = 0; i < len; i++) {

last = SAM_Append(last, root, str[i] - 'a');

}

return root;

}

int cnt[100005];

void toposort(){

memset(cnt, 0, sizeof(cnt));

for (int i = 0; i <= totalNode; i++) {

cnt[idx[i].mxn]++;

}

for (int i = 1; i <= mxmxn; i++) {

cnt[i] += cnt[i-1];

}

for (int i = 0; i <= totalNode; i++) {

idx_sorted[--cnt[idx[i].mxn]] = &idx[i];

}

char a[100005];

int main(){

scanf("%s",a);

SAM_State *sam_root = SAM_Build(a);

toposort();

while (scanf("%s",a) != EOF) {

int len = (int)strlen(a);

SAM_State *sam = sam_root;

int tmp = 0;

for (int i = 0; i < len; i++) {

if (sam -> to[a[i] - 'a'] != NULL) {

tmp++;

sam = sam -> to[a[i] - 'a'];

}else{

while (sam && sam -> to[a[i] - 'a'] == NULL) {

sam = sam -> parent;

}

if (sam == NULL) {

sam = sam_root;

tmp = 0;

}else{

tmp = sam -> mxn + 1;

sam = sam -> to[a[i] - 'a'];

}

sam -> mx = max(sam -> mx, tmp);

}

for (int j = totalNode; j >= 0; j--) {

SAM_State *cur = idx_sorted[j];

cur -> mi = min(cur -> mi, cur -> mx);

if (cur -> parent != NULL) {

cur -> parent -> mx = max(cur -> parent -> mx, cur -> mx);

cur -> parent -> mx = min(cur -> parent -> mxn,cur -> parent -> mx);

}

cur -> mx = 0;

}

int res = 0;

for (int i = 0; i <= totalNode; i++) {

res = max(idx[i].mi, res);

}

printf("%d\n",res);

return 0;

}

HDU 4313 Matrix

July 29, 20152015-07-29hahaschoolLeave a comment

题意

给你一颗树，上面有黑点（母体机器人所在位置），有白点（没有潜伏母体机器人的安全节点），并且给了你每一条边的边权（删边（炸毁道路）需要的时间代价）。现在要你以最小代价删掉一些边，使得没有两个黑点同时可以互相连通。输出这个时间花费即可。

思路

树形DP。这个题和Codeforces 461B Appleman and Tree是一个路子的题，都是在一棵树上不允许同时出现两个联通的特定类别的节点。这种问题我们在思考的时候，方向是将当前的大问题分解成同样的小问题，不断分解到最后，然后考虑怎么样根据一些小问题解得出大问题的解，这是DP的思路所在。

这次，我们设状态表示为 $dp[a][0/1]$ ，其中 $dp[a][0]$ 表示要想让以 $a$ 为根节点的子树满足题目的要求，而且a所在的联通块里面不可以有黑点，需要的最小代价是多少； $dp[a][1]$ 表示要想让以 $a$ 为根节点的子树满足题目要求，且 $a$ 所在的联通块里面有且只有一个黑点，需要的最小代价是多少。

设好了状态，我们开始想DP方程：

我们当前检查的点标号是，我们去逐一检查他的孩子节点，标号是，如果a是一个黑点：
- 因为当前节点是黑点，我们有三种操作可以选：
  - 当前讨论的孩子部分，如果他没有与任何黑点连着，我们可以把这个部分连入当前讨论的根部分，这就是 $dp[b_{i}][0]$ ，即孩子的代价就是根的代价，因为没有切断就没有增加代价。
  - 把根部分和当前讨论的孩子部分中间的边切断，这样的话无论孩子部分到底有没有和黑点连接，都没有关系，只要把孩子的代价加上切断代价就是这样做的代价了，也就是 $dp[b_{i}][0]+cost(a \rightarrow b_{i})$ （孩子部分没有和黑点相连的情况下切断）和 $dp[b_{i}][1]+cost(a \rightarrow b_{i})$ （孩子部分有和黑点相连的情况下切断）。
  - 比较这三种选择，取最优就是局部最优解了。
- $dp[a][0]=\inf$
  黑点不可能不和黑点相连，所以这里用inf屏蔽掉这种选择。
如果a是一个白点：
- 因为当前节点是白色，我们想要让他变成连着黑色的情况，这样的话有四种操作可以选：
  - 假如截止目前和根部连接的所有孩子都不包含黑点，我们可以让现在的这个孩子部分以含有黑点的形态和根部连接，使根部变成有黑点的情况。这就是 $dp[a][0]+dp[b_{i}][1]$ 。
  - 假如当前的根部已经连有黑点，为了满足要求，新联入的部分不可以再包含黑点，这就是 $dp[a][1]+dp[b_{i}][0]$ .
  - 假如孩子部分被切断，这样的话就无所谓孩子长成啥样了，只要算一下代价就可以了，也就是 $dp[b_{i}][0]+cost(a \rightarrow b_{i})$ （孩子部分没有和黑点相连的情况下切断）和 $dp[b_{i}][1]+cost(a \rightarrow b_{i})$ （孩子部分有和黑点相连的情况下切断）。
  - 这四种选择里面选最优的就好了。
- 当前节点是白色，我们想要让她不要根任何黑色连上，这样的话有3种选择：
  - 当前讨论的孩子部分没有和黑色连着，我们可以放心的把这部分连到根部，这就是 $dp[b_{i}][0]$ 。
  - 切断了和孩子部分之间的连接，也就是 $dp[b_{i}][0]+cost(a \rightarrow b_{i})$ （孩子部分没有和黑点相连的情况下切断）和 $dp[b_{i}][1]+cost(a \rightarrow b_{i})$ （孩子部分有和黑点相连的情况下切断）。（其实我已经复制了这一段两遍。。。）
- 注意这两个 $dp[a][0]$ 和 $dp[a][1]$ 要同时处理，因为这里面有一个从“刚才” $dp[a][0]$ 到“现在” $dp[a][1]$ 的转移。

方程想好之后，DFS深入叶子部分，在返回的时候处理好 $dp$ 数组就可以了，最后我们要在 $dp[0][0]$ 和 $dp[0][1]$ 之间取个最小的，因为你所制定的根在最优解的时候连不连黑点并不知道。

代码

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <cmath>
#include <set>
#include <stack>
#include <cmath>
#include <map>

using namespace std;

static long long MAXN = 909303909303;

struct nodeType{
    vector<int> to;
    vector<int> cost;
    int color;
} vertex[100005];

void addEdge(int from,int to,int cost){
    vertex[from].to.push_back(to);
    vertex[from].cost.push_back(cost);
}

long long dp[100005][2];
void dfs(int cur, int par){
    nodeType &currNode = vertex[cur];
    for (int i = 0; i < currNode.to.size(); i++) {
        if (currNode.to[i] != par) {
            dfs(currNode.to[i], cur);
        }
    }
    if (currNode.color == 1) {
        dp[cur][0] = MAXN;
        dp[cur][1] = 0;
        for (int i = 0; i < currNode.to.size(); i++) {
            if (currNode.to[i] != par) {
                dp[cur][1] += min(dp[currNode.to[i]][0],min(dp[currNode.to[i]][0]+currNode.cost[i], dp[currNode.to[i]][1]+currNode.cost[i]));
            }
        }
    }else {
        dp[cur][0] = 0;
        dp[cur][1] = 0;
        for (int i = 0; i < currNode.to.size(); i++) {
            if (currNode.to[i] != par) {
                dp[cur][1] = min(dp[cur][0]+dp[currNode.to[i]][1], min(dp[cur][1]+dp[currNode.to[i]][0],min(dp[cur][1]+dp[currNode.to[i]][0]+currNode.cost[i], dp[cur][1]+dp[currNode.to[i]][1]+currNode.cost[i])));
                dp[cur][0] += min(dp[currNode.to[i]][0], min(dp[currNode.to[i]][0]+currNode.cost[i], dp[currNode.to[i]][1]+currNode.cost[i]));
            }
        }
    }
}

int main(){
    int caseCnt = 0;
    scanf(" %d",&caseCnt);
    while (caseCnt--) {
        int n = 0,k = 0;
        scanf(" %d %d",&n,&k);
        for (int i = 0; i < n; i++) {
            //init
            vertex[i].to.clear();
            vertex[i].cost.clear();
            vertex[i].color = 0;
        }
        for (int i = 0; i < n-1; i++) {
            int a = 0,b = 0,c = 0;
            scanf(" %d %d %d",&a,&b,&c);
            addEdge(a, b, c);
            addEdge(b, a, c);
        }
        for (int i = 0; i < k; i++) {
            int blkpt = 0;
            scanf(" %d",&blkpt);
            vertex[blkpt].color = 1;
        }
        dfs(0, -1);
        cout << min(dp[0][0], dp[0][1]) << endl;
    }
    return 0;
}

#include <iostream>

#include <algorithm>

#include <queue>

#include <vector>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <iomanip>

#include <cmath>

#include <set>

#include <stack>

#include <cmath>

#include <map>

using namespace std;

static long long MAXN = 909303909303;

struct nodeType{

vector<int> to;

vector<int> cost;

int color;

} vertex[100005];

void addEdge(int from,int to,int cost){

vertex[from].to.push_back(to);

vertex[from].cost.push_back(cost);

}

long long dp[100005][2];

void dfs(int cur, int par){

nodeType &currNode = vertex[cur];

for (int i = 0; i < currNode.to.size(); i++) {

if (currNode.to[i] != par) {

dfs(currNode.to[i], cur);

}

if (currNode.color == 1) {

dp[cur][0] = MAXN;

dp[cur][1] = 0;

for (int i = 0; i < currNode.to.size(); i++) {

if (currNode.to[i] != par) {

dp[cur][1] += min(dp[currNode.to[i]][0],min(dp[currNode.to[i]][0]+currNode.cost[i], dp[currNode.to[i]][1]+currNode.cost[i]));

}

}else {

dp[cur][0] = 0;

dp[cur][1] = 0;

for (int i = 0; i < currNode.to.size(); i++) {

if (currNode.to[i] != par) {

dp[cur][1] = min(dp[cur][0]+dp[currNode.to[i]][1], min(dp[cur][1]+dp[currNode.to[i]][0],min(dp[cur][1]+dp[currNode.to[i]][0]+currNode.cost[i], dp[cur][1]+dp[currNode.to[i]][1]+currNode.cost[i])));

dp[cur][0] += min(dp[currNode.to[i]][0], min(dp[currNode.to[i]][0]+currNode.cost[i], dp[currNode.to[i]][1]+currNode.cost[i]));

}

int main(){

int caseCnt = 0;

scanf(" %d",&caseCnt);

while (caseCnt--) {

int n = 0,k = 0;

scanf(" %d %d",&n,&k);

for (int i = 0; i < n; i++) {

//init

vertex[i].to.clear();

vertex[i].cost.clear();

vertex[i].color = 0;

}

for (int i = 0; i < n-1; i++) {

int a = 0,b = 0,c = 0;

scanf(" %d %d %d",&a,&b,&c);

addEdge(a, b, c);

addEdge(b, a, c);

}

for (int i = 0; i < k; i++) {

int blkpt = 0;

scanf(" %d",&blkpt);

vertex[blkpt].color = 1;

}

dfs(0, -1);

cout << min(dp[0][0], dp[0][1]) << endl;

}

return 0;

}

一份仅用于学习的伸展树C实现

April 24, 20152015-04-24hahaschoolLeave a comment

这份代码来自于以前的Wikipedia，遇到这份代码也许是缘分吧，虽然实现上十分的冗长（好多好多的废话），但是也正因为如此这份代码展示了伸展树操作的每一个细节，尽管没什么实用价值，但是拿来理解splay是很好的。我自己抄了一遍同时加上了注释。

//
//  SplayTree.cpp
//  playground
//
//  Created by Adam Chang on 2015/4/11.
//  Copyright (c) 2015年 Adam Chang. All rights reserved.
//

//C Implementation in reference of http://en.wikipedia.org/w/index.php?title=Splay_tree&oldid=533723000
//NON-Recursive Elementary

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <cmath>
#include <set>
#include <stack>
#include <cmath>

using namespace std;

struct node{
    int data;
    node *left;
    node *right;
    node *parent;
};

struct node *rotate_left(struct node *pivot,struct node *root){
    struct node *x;
    x = pivot->right;
    //reassign x's left child to pivot's right child slot
    pivot->right = x->left;
    if (x->left != NULL) {
        x->left->parent = pivot;
    }
    //reverse the parential relation between x and pivot
    x->left = pivot;
    if (pivot->parent != NULL) {
        if (pivot == pivot->parent->left) {
            pivot->parent->left = x;
        }else{
            pivot->parent->right = x;
        }
    }
    x->parent = pivot->parent;
    pivot->parent = x;
    //return value for the splay func to change the tree root
    if (pivot == root) {
        //pivot is the original root,after rotate x become the new root
        return x;
    }else{
        return root;
    }
}

struct node *rotate_right(struct node *pivot,struct node *root){
    //x is pivot's left child
    struct node *x;
    x = pivot->left;
    //assign x's right child to pivot's left child slot
    pivot->left = x -> right;
    if (x->right != NULL) {
        x->right->parent = pivot;
    }
    //reverse the parental relationship between x and pivot
    x->right = pivot;
    if (pivot->parent != NULL) {
        if (pivot == pivot->parent->right) {
            pivot->parent->right = x;
        }else {
            pivot->parent->left = x;
        }
    }
    x->parent = pivot->parent;
    pivot->parent = x;
    //the return value is for the splay func to change the tree root
    if (pivot == root) {
        //pivot is the original root,after rotate x become the new root
        return x;
    }else{
        return root;
    }
}

void splay(struct node *x,struct node *root){
    //x is root,no operation required
    if (x == root) {
        return;
    }else if(x->parent == root){
        //single rotation required
        if (x == x->parent->left) {
            //x on the root's left,let root be the pivot and throw the x onto the root pos
            root = rotate_right(root, root);
        }else{
            //conversely
            root = rotate_left(root, root);
        }
    }else {
        //complex situation,multiple rotation required
        node *p,*g;//p:parent node g:grandparent node
        p = x->parent;
        g = p->parent;
        if (x == p->left && p == g->left) {
            //double right rotation
            root = rotate_right(g, root);
            root = rotate_right(p, root);
        }else if(x == p->right && p == g->right){
            //double left rotation
            root = rotate_left(g, root);
            root = rotate_left(p, root);
        }else if(x == p->left && p == g->right){
            //perform right-left(zagzig) rotation
            root = rotate_right(p, root);
            root = rotate_left(g, root);
        }else if(x == p->right && p == g->left){
            //perform left-right(zigzag) rotation
            root = rotate_left(p, root);
            root = rotate_right(g, root);
        }
        //when in complex situation,the splay cannot terminate only after once,use recursion here.
        splay(x, root);
    }
}

struct node *insert(struct node *root,int value){
    struct node *temp1,*temp2,*par;
    if (root == NULL) {
        //given subtree root doesn't exist,create one and return this new subroot for splay.
        root = (struct node *)malloc(sizeof(struct node));
        if (root != NULL) {
            root->data = value;
            root->parent = NULL;
            root->left = NULL;
            root->right = NULL;
        }else{
            //handle memory exception
            printf("MEMORY ALLOCATION EXCEPTION\n");
            exit(0);
        }
    }else{
        temp2 = root;
        while (temp2 != NULL) {
            //iteriate until we find a good place to place the new node
            temp1 = temp2;//save current node as the target node(or its place)'s parent
            if (temp2->data > value) {
                temp2 = temp2->left;
            }else if(temp2->data < value){
                temp2 = temp2->right;
            }else{
                //temp2->data==value no need to instert,just return this node
                //(we don't accept nodes with same key),in this case insert becomes search
                return temp2;
            }
        }
        if (temp1->data > value) {
            par = temp1;//par is now the target's parent
            temp1->left = (struct node *)malloc(sizeof(struct node));
            temp1 = temp1->left;//temp1 is now the target node
            if (temp1 != NULL) {
                temp1->data = value;
                temp1->parent = par;
                temp1->left = NULL;
                temp1->right = NULL;
            }else{
                //handle memory exception
                printf("MEMORY ALLOCATION EXCEPTION\n");
                exit(0);
            }
        }else{
            //only repeating itself(REFACTORIZATION REQUIRED)
            par = temp1;//par is now the target's parent
            temp1->right = (struct node *)malloc(sizeof(struct node));
            temp1 = temp1->right;//temp1 is now the target node
            if (temp1 != NULL) {
                temp1->data = value;
                temp1->parent = par;
                temp1->left = NULL;
                temp1->right = NULL;
            }else{
                //handle memory exception
                printf("MEMORY ALLOCATION EXCEPTION\n");
                exit(0);
            }
        }
    }
    splay(temp1, root);//splay the newly inserted node to root position
    return temp1;//this func. returns the pointer of newly inserted node for futher ops.
}

struct node *lookup(struct node *root,int value){
    struct node *temp1,*temp2;
    if (root != NULL) {
        temp1 = root;//temp2 is the target pos for return,temp1 is only for iteration
        temp2 = temp1;
        while (temp1 != NULL) {
            temp2 = temp1;
            if (temp1->data > value) {
                temp1 = temp1->left;
            }else if(temp1->data < value){
                temp1 = temp1->right;
            }else{
                return temp1;//already found,just return it.
            }
        }
        return temp2;//didn't find the node but we find it's parent(assuming the node exists),return the parent;
    }else{
        printf("ROOT NULL EXCEPTION\n");
        exit(0);
    }
}

struct node *successor(struct node *x){
    //get the assuming node's right subtree's leftmost child
    struct node *temp1,*temp2;
    temp1 = temp2 = x->right;
    while (temp1 != NULL) {
        temp2 = temp1;
        temp1 = temp1->left;
    }
    return temp2;
}

struct node *remove(struct node *root,int value){
    struct node *x,*y,*s;//y is the new root after removal
    x = lookup(root, value);
    if (x->data == value) {
        //we have located the node matched for remove
        if (x->left == NULL && x->right == NULL) {
            if (x == root) {
                //special judge to avoid root fault
                y = root = NULL;//if root is leaf,simply make NULL the new root
            }else{
                //if the node for remove is a leaf
                y = x->parent;
                if (x == (y->right)) {
                    y->right = NULL;
                }else{
                    y->left = NULL;
                }//unlink x from its parent
            }
        }else if(x->left != NULL && x->right == NULL){
            if (x == root) {//root fault prevention
                x->left->parent = NULL;//x's lch becomes the new root
                y = x->left;
                root = x->left;
            }else{
                //if the node for removal only have left child
                y = x->parent;
                if (x == y->left) {
                    x->left->parent = y;//relink the child
                    y->left = x->left;
                }else{
                    x->left->parent = y;//relink
                    y->right = x->left;
                }
            }
        }else if(x->left == NULL && x->right != NULL){
            if(x == root) {
                //avoid root fault
                x->right->parent=NULL;//x's rch becomes the new root
                y=x->right;
                root=x->right;
            }
            else {
                //if the node to remove only have right child
                y = x->parent;
                //we just repeat ourself as above...
                if (x == y->left) {
                    x->right->parent = y;
                    y->left = x->right;
                }else{
                    x->right->parent = y;
                    y->right = x->right;
                }
            }
        }else{
            //if the node for removal have both childs
            if (x == root) {
                s = successor(x);//find successor(rch's leftmost node)
                if (s == x->right) {
                    //if successor is right at x's rch
                    y = s;
                    s->parent = NULL;//make s the new root,relink x's lch
                    x->left->parent = s;
                    s->left = x->left;
                    root = s;
                }else{
                    y = s->parent;//s's parent should be the new root after splay
                    if (s->right != NULL) {
                        s->right->parent = y;//relink s's rch to s's parent(because s goes to root)
                        y->left = s->right;
                    }else{
                        y->left = NULL;//unlink s's parent's lch
                    }
                    s->parent = NULL;//s is now the new root
                    x->right->parent = s;//relink
                    x->left->parent = s;
                    s->right = x->right;
                    s->left = x->left;
                    root = s;
                }
            }else{
                y = x->parent;
                if (x == y->left) {
                    s = successor(x); //find x's right's leftmost to replace x
                    if (s != x->right) {
                        y = s->parent;
                        if (s->right != NULL) {
                            //if the successor have right child
                            s->right->parent = y;//relink its right child to x's parent(s goes to x's parent's left)
                            y->left = s->right;
                        }else{
                            y->left = NULL;
                        }
                        s->parent = s->parent;//the relink proccess can be better understood by illustration
                        x->right->parent = s;
                        x->left->parent = s;
                        s->right = x->right;
                        s->left = x->left;
                        x->parent->left = s;
                    }else{
                        y = s;
                        s->parent = x->parent;
                        x->left->parent = s;
                        s->left = x->left;
                        x->parent->left = s;
                    }
                }else{
                    s = successor(x);//we are repeating
                    if (s != x->right) {
                        y = s->parent;
                        if (s->right != NULL) {
                            s->right->parent = y;
                            y->left = s->right;
                        }else{
                            y->left = NULL;
                        }
                        s->parent = x->parent;
                        s->right->parent = s;
                        x->left->parent = s;
                        s->right = x->right;
                        s->left = x->left;
                        x->parent->right = s;
                    }else{
                        y = s;
                        s->parent = x->parent;
                        s->left->parent = s;
                        s->left = x->left;
                        x->parent->right = s;
                    }
                }
            }
        }
        free(x);//destroy and free
        splay(y, root);//splay y to the new root's position
        return y;
    }else{
        splay(x, root);//found nothing to delete,but still we should splay
        return x;
    }
}


int main(){

    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

236

237

238

239

240

241

242

243

244

245

246

247

248

249

250

251

252

253

254

255

256

257

258

259

260

261

262

263

264

265

266

267

268

269

270

271

272

273

274

275

276

277

278

279

280

281

282

283

284

285

286

287

288

289

290

291

292

293

294

295

296

297

298

299

300

301

302

303

304

305

306

307

308

309

310

311

312

313

314

315

316

317

318

319

320

321

322

323

324

325

326

327

328

329

330

331

332

333

334

335

336

337

338

339

340

341

342

343

344

345

346

347

348

349

350

351

352

353

354

355

356

357

358

359

360

361

362

363

364

365

366

367

368

369

370

371

372

373

374

375

// SplayTree.cpp

// playground

// Created by Adam Chang on 2015/4/11.

//C Implementation in reference of http://en.wikipedia.org/w/index.php?title=Splay_tree&oldid=533723000

//NON-Recursive Elementary

#include <iostream>

#include <algorithm>

#include <queue>

#include <vector>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <iomanip>

#include <cmath>

#include <set>

#include <stack>

#include <cmath>

using namespace std;

struct node{

int data;

node *left;

node *right;

node *parent;

};

struct node *rotate_left(struct node *pivot,struct node *root){

struct node *x;

x = pivot->right;

//reassign x's left child to pivot's right child slot

pivot->right = x->left;

if (x->left != NULL) {

x->left->parent = pivot;

}

//reverse the parential relation between x and pivot

x->left = pivot;

if (pivot->parent != NULL) {

if (pivot == pivot->parent->left) {

pivot->parent->left = x;

}else{

pivot->parent->right = x;

}

x->parent = pivot->parent;

pivot->parent = x;

//return value for the splay func to change the tree root

if (pivot == root) {

//pivot is the original root,after rotate x become the new root

return x;

}else{

return root;

}

struct node *rotate_right(struct node *pivot,struct node *root){

//x is pivot's left child

struct node *x;

x = pivot->left;

//assign x's right child to pivot's left child slot

pivot->left = x -> right;

if (x->right != NULL) {

x->right->parent = pivot;

}

//reverse the parental relationship between x and pivot

x->right = pivot;

if (pivot->parent != NULL) {

if (pivot == pivot->parent->right) {

pivot->parent->right = x;

}else {

pivot->parent->left = x;

}

x->parent = pivot->parent;

pivot->parent = x;

//the return value is for the splay func to change the tree root

if (pivot == root) {

//pivot is the original root,after rotate x become the new root

return x;

}else{

return root;

}

void splay(struct node *x,struct node *root){

//x is root,no operation required

if (x == root) {

return;

}else if(x->parent == root){

//single rotation required

if (x == x->parent->left) {

//x on the root's left,let root be the pivot and throw the x onto the root pos

root = rotate_right(root, root);

}else{

//conversely

root = rotate_left(root, root);

}

}else {

//complex situation,multiple rotation required

node *p,*g;//p:parent node g:grandparent node

p = x->parent;

g = p->parent;

if (x == p->left && p == g->left) {

//double right rotation

root = rotate_right(g, root);

root = rotate_right(p, root);

}else if(x == p->right && p == g->right){

//double left rotation

root = rotate_left(g, root);

root = rotate_left(p, root);

}else if(x == p->left && p == g->right){

//perform right-left(zagzig) rotation

root = rotate_right(p, root);

root = rotate_left(g, root);

}else if(x == p->right && p == g->left){

//perform left-right(zigzag) rotation

root = rotate_left(p, root);

root = rotate_right(g, root);

}

//when in complex situation,the splay cannot terminate only after once,use recursion here.

splay(x, root);

}

struct node *insert(struct node *root,int value){

struct node *temp1,*temp2,*par;

if (root == NULL) {

//given subtree root doesn't exist,create one and return this new subroot for splay.

root = (struct node *)malloc(sizeof(struct node));

if (root != NULL) {

root->data = value;

root->parent = NULL;

root->left = NULL;

root->right = NULL;

}else{

//handle memory exception

printf("MEMORY ALLOCATION EXCEPTION\n");

exit(0);

}

}else{

temp2 = root;

while (temp2 != NULL) {

//iteriate until we find a good place to place the new node

temp1 = temp2;//save current node as the target node(or its place)'s parent

if (temp2->data > value) {

temp2 = temp2->left;

}else if(temp2->data < value){

temp2 = temp2->right;

}else{

//temp2->data==value no need to instert,just return this node

//(we don't accept nodes with same key),in this case insert becomes search

return temp2;

}

if (temp1->data > value) {

par = temp1;//par is now the target's parent

temp1->left = (struct node *)malloc(sizeof(struct node));

temp1 = temp1->left;//temp1 is now the target node

if (temp1 != NULL) {

temp1->data = value;

temp1->parent = par;

temp1->left = NULL;

temp1->right = NULL;

}else{

//handle memory exception

printf("MEMORY ALLOCATION EXCEPTION\n");

exit(0);

}

}else{

//only repeating itself(REFACTORIZATION REQUIRED)

par = temp1;//par is now the target's parent

temp1->right = (struct node *)malloc(sizeof(struct node));

temp1 = temp1->right;//temp1 is now the target node

if (temp1 != NULL) {

temp1->data = value;

temp1->parent = par;

temp1->left = NULL;

temp1->right = NULL;

}else{

//handle memory exception

printf("MEMORY ALLOCATION EXCEPTION\n");

exit(0);

}

splay(temp1, root);//splay the newly inserted node to root position

return temp1;//this func. returns the pointer of newly inserted node for futher ops.

}

struct node *lookup(struct node *root,int value){

struct node *temp1,*temp2;

if (root != NULL) {

temp1 = root;//temp2 is the target pos for return,temp1 is only for iteration

temp2 = temp1;

while (temp1 != NULL) {

temp2 = temp1;

if (temp1->data > value) {

temp1 = temp1->left;

}else if(temp1->data < value){

temp1 = temp1->right;

}else{

return temp1;//already found,just return it.

}

return temp2;//didn't find the node but we find it's parent(assuming the node exists),return the parent;

}else{

printf("ROOT NULL EXCEPTION\n");

exit(0);

}

struct node *successor(struct node *x){

//get the assuming node's right subtree's leftmost child

struct node *temp1,*temp2;

temp1 = temp2 = x->right;

while (temp1 != NULL) {

temp2 = temp1;

temp1 = temp1->left;

}

return temp2;

}

struct node *remove(struct node *root,int value){

struct node *x,*y,*s;//y is the new root after removal

x = lookup(root, value);

if (x->data == value) {

//we have located the node matched for remove

if (x->left == NULL && x->right == NULL) {

if (x == root) {

//special judge to avoid root fault

y = root = NULL;//if root is leaf,simply make NULL the new root

}else{

//if the node for remove is a leaf

y = x->parent;

if (x == (y->right)) {

y->right = NULL;

}else{

y->left = NULL;

}//unlink x from its parent

}

}else if(x->left != NULL && x->right == NULL){

if (x == root) {//root fault prevention

x->left->parent = NULL;//x's lch becomes the new root

y = x->left;

root = x->left;

}else{

//if the node for removal only have left child

y = x->parent;

if (x == y->left) {

x->left->parent = y;//relink the child

y->left = x->left;

}else{

x->left->parent = y;//relink

y->right = x->left;

}

}else if(x->left == NULL && x->right != NULL){

if(x == root) {

//avoid root fault

x->right->parent=NULL;//x's rch becomes the new root

y=x->right;

root=x->right;

}

else {

//if the node to remove only have right child

y = x->parent;

//we just repeat ourself as above...

if (x == y->left) {

x->right->parent = y;

y->left = x->right;

}else{

x->right->parent = y;

y->right = x->right;

}

}else{

//if the node for removal have both childs

if (x == root) {

s = successor(x);//find successor(rch's leftmost node)

if (s == x->right) {

//if successor is right at x's rch

y = s;

s->parent = NULL;//make s the new root,relink x's lch

x->left->parent = s;

s->left = x->left;

root = s;

}else{

y = s->parent;//s's parent should be the new root after splay

if (s->right != NULL) {

s->right->parent = y;//relink s's rch to s's parent(because s goes to root)

y->left = s->right;

}else{

y->left = NULL;//unlink s's parent's lch

}

s->parent = NULL;//s is now the new root

x->right->parent = s;//relink

x->left->parent = s;

s->right = x->right;

s->left = x->left;

root = s;

}

}else{

y = x->parent;

if (x == y->left) {

s = successor(x); //find x's right's leftmost to replace x

if (s != x->right) {

y = s->parent;

if (s->right != NULL) {

//if the successor have right child

s->right->parent = y;//relink its right child to x's parent(s goes to x's parent's left)

y->left = s->right;

}else{

y->left = NULL;

}

s->parent = s->parent;//the relink proccess can be better understood by illustration

x->right->parent = s;

x->left->parent = s;

s->right = x->right;

s->left = x->left;

x->parent->left = s;

}else{

y = s;

s->parent = x->parent;

x->left->parent = s;

s->left = x->left;

x->parent->left = s;

}

}else{

s = successor(x);//we are repeating

if (s != x->right) {

y = s->parent;

if (s->right != NULL) {

s->right->parent = y;

y->left = s->right;

}else{

y->left = NULL;

}

s->parent = x->parent;

s->right->parent = s;

x->left->parent = s;

s->right = x->right;

s->left = x->left;

x->parent->right = s;

}else{

y = s;

s->parent = x->parent;

s->left->parent = s;

s->left = x->left;

x->parent->right = s;

}

free(x);//destroy and free

splay(y, root);//splay y to the new root's position

return y;

}else{

splay(x, root);//found nothing to delete,but still we should splay

return x;

}

int main(){

return 0;

}