树DP – hahaschool

POJ 2114 Boatherds

December 06, 20152015-12-06hahaschoolLeave a comment

题意

给出一棵树，树边带有边权，问你能不能找出一条路径使得路径边权之和正好等于给出的k值。

思路

和这个题非常像，只不过题意从计算有多少点对之间距离小于k换成了判断有没有一条路径等于k。但实际上可以用一套思路解决。

代码

#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>
#include <complex>

using namespace std;

const int MAXV = 100005;
const int MAXE = 200005;
const int INF = 0x3f3f3f3f;

int nxt[MAXE],end[MAXE],head[MAXV],cost[MAXE],gtot,vis[MAXV];
int n;

void init(){
    gtot = 2;
    for(int i = 1; i<=n; i++){
        head[i] = 0;
    }
}
void addEdge(int from,int to,int _cost){
    end[gtot] = to;
    cost[gtot] = _cost;
    nxt[gtot] = head[from];
    head[from] = gtot++;
}

int siz[MAXV],midpn,bal;
void getbal(int cur,int par,int totsiz){
    siz[cur] = 1;
    int dpn = 1;
    for(int j = head[cur]; j; j = nxt[j]){
        int now = end[j];
        if(now != par && !vis[now]){
            getbal(now,cur,totsiz);
            siz[cur] += siz[now];
            dpn = max(dpn,siz[now]);
        }
    }
    dpn = max(dpn,totsiz-siz[cur]);
    if(dpn < midpn){
        midpn = dpn;
        bal = cur;
    }
}

int dis[MAXV],distot;
void dfs_dis(int cur,int par,int hav = 0){
    dis[distot++] = hav;
    siz[cur] = 1;
    for(int j = head[cur]; j; j = nxt[j]){
        int now = end[j];
        if(now != par && !vis[now]){
            dfs_dis(now,cur,hav+cost[j]);
            siz[cur] += siz[now];
        }
    }
}

int calc(int rt,int k){
    int ret = 0;
    distot = 0;
    dfs_dis(rt,0);
    sort(dis,dis+distot);
    for(int i = 0; i < distot; i++){
        pair<int*,int*> bin = equal_range(dis+i+1,dis+distot,k-dis[i]);
        ret += bin.second - bin.first;
    }
    return ret;
}

bool dfs_main(int cur,int k){
    int cnt = 0;
    cnt += calc(cur,k);
    vis[cur] = true;
    for(int j = head[cur]; j; j = nxt[j]){
        int now = end[j];
        if(!vis[now]){
            cnt -= calc(now,k-2*cost[j]);
        }
    }
    if(cnt > 0){
        return true;
    }else{
        for(int j = head[cur]; j; j = nxt[j]){
            int now = end[j];
            if(!vis[now]){
                midpn = INF;
                getbal(now,cur,siz[now]);
                if(dfs_main(bal,k)){
                    return true;
                }
            }
        }
    }
    return false;
}

bool solve(int k){
    for(int i = 1; i<= n; i++){
        vis[i] = false;
    }
    midpn = INF;
    getbal(1,0,n);
    return dfs_main(bal,k);
}


int main(){
    while(scanf(" %d",&n) != EOF && n){
        init();
        for(int i = 1; i <= n; i++){
            int a,b;
            while(scanf(" %d",&a) != EOF && a){
                scanf(" %d",&b);
                addEdge(i,a,b);
                addEdge(a,i,b);
            }
        }
        int q;
        while(scanf(" %d",&q) != EOF && q){
            if(solve(q)){
                puts("AYE");
            }else{
                puts("NAY");
            }
        }
        puts(".");
    }

}

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

#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>

#include <complex>

using namespace std;

const int MAXV = 100005;

const int MAXE = 200005;

const int INF = 0x3f3f3f3f;

int nxt[MAXE],end[MAXE],head[MAXV],cost[MAXE],gtot,vis[MAXV];

int n;

void init(){

gtot = 2;

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

head[i] = 0;

}

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

end[gtot] = to;

cost[gtot] = _cost;

nxt[gtot] = head[from];

head[from] = gtot++;

}

int siz[MAXV],midpn,bal;

void getbal(int cur,int par,int totsiz){

siz[cur] = 1;

int dpn = 1;

for(int j = head[cur]; j; j = nxt[j]){

int now = end[j];

if(now != par && !vis[now]){

getbal(now,cur,totsiz);

siz[cur] += siz[now];

dpn = max(dpn,siz[now]);

}

dpn = max(dpn,totsiz-siz[cur]);

if(dpn < midpn){

midpn = dpn;

bal = cur;

}

int dis[MAXV],distot;

void dfs_dis(int cur,int par,int hav = 0){

dis[distot++] = hav;

siz[cur] = 1;

for(int j = head[cur]; j; j = nxt[j]){

int now = end[j];

if(now != par && !vis[now]){

dfs_dis(now,cur,hav+cost[j]);

siz[cur] += siz[now];

}

int calc(int rt,int k){

int ret = 0;

distot = 0;

dfs_dis(rt,0);

sort(dis,dis+distot);

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

pair<int*,int*> bin = equal_range(dis+i+1,dis+distot,k-dis[i]);

ret += bin.second - bin.first;

}

return ret;

}

bool dfs_main(int cur,int k){

int cnt = 0;

cnt += calc(cur,k);

vis[cur] = true;

for(int j = head[cur]; j; j = nxt[j]){

int now = end[j];

if(!vis[now]){

cnt -= calc(now,k-2*cost[j]);

}

if(cnt > 0){

return true;

}else{

for(int j = head[cur]; j; j = nxt[j]){

int now = end[j];

if(!vis[now]){

midpn = INF;

getbal(now,cur,siz[now]);

if(dfs_main(bal,k)){

return true;

}

return false;

}

bool solve(int k){

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

vis[i] = false;

}

midpn = INF;

getbal(1,0,n);

return dfs_main(bal,k);

}

int main(){

while(scanf(" %d",&n) != EOF && n){

init();

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

int a,b;

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

scanf(" %d",&b);

addEdge(i,a,b);

addEdge(a,i,b);

}

int q;

while(scanf(" %d",&q) != EOF && q){

if(solve(q)){

puts("AYE");

}else{

puts("NAY");

}

puts(".");

}

POJ 1987 Distance Statistics

December 06, 20152015-12-06hahaschoolOne Comment

题意

给出一棵树，和树上两点之间的边权大小，要你快速回答出树上有多少不同的点对使的这对点之间的距离至多为k。

思路

典型的点分治问题。

当考虑一棵有根树中有多少点对的距离小于等于k时，可以求出所有节点到根部的距离，然后使用二分，或者尺取的方法得到有多少对点之间的距离小于等于k。但是在上面的计算过程中我们想要求的是经过根部的符合要求的点对数量，但实际上多算入了一些并不符合要求的点，同时也漏掉了不经过根部的符合条件的点对。

所以我们可以这样看：一棵树的符合条件点对数=上面所述方法找出的点对数-各个子树中两点间距小于等于(k-2e)的点对数目(e是根部到孩子的树边的边权)+各个子树符合条件的点对数

上面的式子是递归的，这是一个树分治（点分治）策略。

在实现树分治的时候，一定要注意只有配合了重心的点分治才能达到O(nlogn)的复杂度，否则会面临特殊情况（比如链）退化到O(n^2).

代码

#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>
#include <complex>

using namespace std;

const int MAXV = 40005;
const int MAXE = 80005;

int N,M,K;

int head[MAXV],nxt[MAXE],to[MAXE],len[MAXE],vis[MAXV],gphtot;
void gph_init(){
    gphtot = 2;
    memset(head,0,sizeof(head));
    memset(vis,0,sizeof(vis));
}
void gph_addEdge(int from,int _to,int cost){
    to[gphtot] = _to;
    nxt[gphtot] = head[from];
    len[gphtot] = cost;
    head[from] = gphtot++;
}
void input(){
    scanf(" %d %d",&N,&M);
    gph_init();
    for(int i = 1; i <= M; i++){
        int a,b,c;
        char d;
        scanf(" %d %d %d %c",&a,&b,&c,&d);
        gph_addEdge(a,b,c);
        gph_addEdge(b,a,c);
    }
    scanf(" %d",&K);
}

int siz[MAXV],mic,bal;
void getbal(int cur,int par,int totsiz){
    int mxc = 0;
    siz[cur] = 1;
    for(int j = head[cur]; j; j = nxt[j]){
        int now = to[j];
        if(now != par && !vis[now]){
            getbal(now,cur,totsiz);
            siz[cur] += siz[now];
            mxc = max(mxc,siz[now]);
        }
    }
    mxc = max(mxc,totsiz - siz[cur]);
    if(mic > mxc){
        mic = mxc;
        bal = cur;
    }
}

int dis[MAXV],distot;
void dfs_dis(int cur,int par,int hav = 0){
    dis[distot++] = hav;
    siz[cur] = 1;
    for(int j = head[cur]; j; j = nxt[j]){
        int now = to[j];
        if(now != par && !vis[now]){
            dfs_dis(now,cur,hav+len[j]);
            siz[cur] += siz[now];
        }
    }
}
int calc(int rt,int k){
    distot = 0;
    dfs_dis(rt,0,k);
    int ret = 0;
    sort(dis,dis+distot);
    int r = distot - 1;
    for(int l = 0; l < distot; l++){
        while(dis[r] + dis[l] > K){
            r--;
        }
        if(r <= l){
            break;
        }
        ret += r-l;
    }
    return ret;
}
int res;
void dfs_main(int cur){
    res += calc(cur,0);
    vis[cur] = true;
    for(int j = head[bal]; j; j = nxt[j]){
        int now = to[j];
        if(!vis[now]){
            res -= calc(now,len[j]);
            mic = 0x3f3f3f3f;
            getbal(now,cur,siz[now]);
            dfs_main(bal);
        }
    }
}
void solve(){
    res = 0;
    mic = 0x3f3f3f3f;
    getbal(1,0,N);
    dfs_main(bal);
    printf("%d\n",res);
}

int main(){
    input();
    solve();
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

#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>

#include <complex>

using namespace std;

const int MAXV = 40005;

const int MAXE = 80005;

int N,M,K;

int head[MAXV],nxt[MAXE],to[MAXE],len[MAXE],vis[MAXV],gphtot;

void gph_init(){

gphtot = 2;

memset(head,0,sizeof(head));

memset(vis,0,sizeof(vis));

}

void gph_addEdge(int from,int _to,int cost){

to[gphtot] = _to;

nxt[gphtot] = head[from];

len[gphtot] = cost;

head[from] = gphtot++;

}

void input(){

scanf(" %d %d",&N,&M);

gph_init();

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

int a,b,c;

char d;

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

gph_addEdge(a,b,c);

gph_addEdge(b,a,c);

}

scanf(" %d",&K);

}

int siz[MAXV],mic,bal;

void getbal(int cur,int par,int totsiz){

int mxc = 0;

siz[cur] = 1;

for(int j = head[cur]; j; j = nxt[j]){

int now = to[j];

if(now != par && !vis[now]){

getbal(now,cur,totsiz);

siz[cur] += siz[now];

mxc = max(mxc,siz[now]);

}

mxc = max(mxc,totsiz - siz[cur]);

if(mic > mxc){

mic = mxc;

bal = cur;

}

int dis[MAXV],distot;

void dfs_dis(int cur,int par,int hav = 0){

dis[distot++] = hav;

siz[cur] = 1;

for(int j = head[cur]; j; j = nxt[j]){

int now = to[j];

if(now != par && !vis[now]){

dfs_dis(now,cur,hav+len[j]);

siz[cur] += siz[now];

}

int calc(int rt,int k){

distot = 0;

dfs_dis(rt,0,k);

int ret = 0;

sort(dis,dis+distot);

int r = distot - 1;

for(int l = 0; l < distot; l++){

while(dis[r] + dis[l] > K){

r--;

}

if(r <= l){

break;

}

ret += r-l;

}

return ret;

}

int res;

void dfs_main(int cur){

res += calc(cur,0);

vis[cur] = true;

for(int j = head[bal]; j; j = nxt[j]){

int now = to[j];

if(!vis[now]){

res -= calc(now,len[j]);

mic = 0x3f3f3f3f;

getbal(now,cur,siz[now]);

dfs_main(bal);

}

void solve(){

res = 0;

mic = 0x3f3f3f3f;

getbal(1,0,N);

dfs_main(bal);

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

}

int main(){

input();

solve();

}

POJ 3107 Godfather

December 06, 20152015-12-06hahaschoolLeave a comment

题意

变相考察树的重心。

思路

请参考这个题和／或这个题

代码

#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>
#include <complex>

using namespace std;

const int MAXV = 50005;
const int MAXE = 100005;

struct Graph {
    int siz[MAXV];
    int dp[MAXV];
    int par[MAXV];

    int head[MAXV];
    int nxt[MAXE];
    int end[MAXE];
    int tot;
    void init() {
        memset(head,0,sizeof(head));
        tot = 2;
    }
    void addEdge(int from,int to) {
        end[tot] = to;
        nxt[tot] = head[from];
        head[from] = tot++;
    }
} gph;

int n;

void dfs(int cur,int par) {
    gph.par[cur] = par;
    gph.siz[cur] = 1;
    gph.dp[cur] = 1;
    for(int j = gph.head[cur]; j; j = gph.nxt[j]) {
        int now = gph.end[j];
        if(now != par) {
            dfs(now,cur);
            gph.siz[cur] += gph.siz[now];
            gph.dp[cur] = max(gph.siz[now],gph.dp[cur]);
        }
    }
}


vector<int> res;
int balance() {
    dfs(1,0);
    int ret = -1;
    for(int i = 1; i <= n; i++) {
        int dpn = max(gph.dp[i],n-gph.siz[i]);
        if(dpn <= n/2) {
            res.push_back(i);
            ret = 0;
        }
    }
    return ret;
}



int main() {
    scanf(" %d",&n);
    gph.init();
    for(int i = 1; i < n ; i++) {
        int a,b;
        scanf(" %d %d",&a,&b);
        gph.addEdge(a,b);
        gph.addEdge(b,a);
    }
    balance();
    for(int i = 0; i < res.size(); i++){
        printf("%d",res[i]);
        if(i == res.size()-1){
            puts("");
        }else{
            putchar(' ');
        }
    }
    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>

#include <complex>

using namespace std;

const int MAXV = 50005;

const int MAXE = 100005;

struct Graph {

int siz[MAXV];

int dp[MAXV];

int par[MAXV];

int head[MAXV];

int nxt[MAXE];

int end[MAXE];

int tot;

void init() {

memset(head,0,sizeof(head));

tot = 2;

}

void addEdge(int from,int to) {

end[tot] = to;

nxt[tot] = head[from];

head[from] = tot++;

}

} gph;

int n;

void dfs(int cur,int par) {

gph.par[cur] = par;

gph.siz[cur] = 1;

gph.dp[cur] = 1;

for(int j = gph.head[cur]; j; j = gph.nxt[j]) {

int now = gph.end[j];

if(now != par) {

dfs(now,cur);

gph.siz[cur] += gph.siz[now];

gph.dp[cur] = max(gph.siz[now],gph.dp[cur]);

}

vector<int> res;

int balance() {

dfs(1,0);

int ret = -1;

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

int dpn = max(gph.dp[i],n-gph.siz[i]);

if(dpn <= n/2) {

res.push_back(i);

ret = 0;

}

return ret;

}

int main() {

scanf(" %d",&n);

gph.init();

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

int a,b;

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

gph.addEdge(a,b);

gph.addEdge(b,a);

}

balance();

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

printf("%d",res[i]);

if(i == res.size()-1){

puts("");

}else{

putchar(' ');

}

return 0;

}

POJ 2378 Tree Cutting

December 06, 20152015-12-06hahaschoolLeave a comment

题意

变相考察求树的重心。

思路

和这个题一致

代码

#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>
#include <complex>

using namespace std;

const int MAXV = 20005;
const int MAXE = 40005;

struct Graph {
    int siz[MAXV];
    int dp[MAXV];
    int par[MAXV];

    int head[MAXV];
    int nxt[MAXE];
    int end[MAXE];
    int tot;
    void init() {
        memset(head,0,sizeof(head));
        tot = 2;
    }
    void addEdge(int from,int to) {
        end[tot] = to;
        nxt[tot] = head[from];
        head[from] = tot++;
    }
} gph;

int n;

void dfs(int cur,int par) {
    gph.par[cur] = par;
    gph.siz[cur] = 1;
    gph.dp[cur] = 1;
    for(int j = gph.head[cur]; j; j = gph.nxt[j]) {
        int now = gph.end[j];
        if(now != par) {
            dfs(now,cur);
            gph.siz[cur] += gph.siz[now];
            gph.dp[cur] = max(gph.siz[now],gph.dp[cur]);
        }
    }
}

int balance() {
    dfs(1,0);
    int ret = -1;
    for(int i = 1; i <= n; i++) {
        int dpn = max(gph.dp[i],n-gph.siz[i]);
        if(dpn <= n/2) {
            printf("%d\n",i);
            ret = 0;
        }
    }
    return ret;
}



int main() {
    scanf(" %d",&n);
    gph.init();
    for(int i = 1; i < n ; i++) {
        int a,b;
        scanf(" %d %d",&a,&b);
        gph.addEdge(a,b);
        gph.addEdge(b,a);
    }
    int res = balance();
    if(res == -1) {
        puts("NONE");
    }
    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>

#include <complex>

using namespace std;

const int MAXV = 20005;

const int MAXE = 40005;

struct Graph {

int siz[MAXV];

int dp[MAXV];

int par[MAXV];

int head[MAXV];

int nxt[MAXE];

int end[MAXE];

int tot;

void init() {

memset(head,0,sizeof(head));

tot = 2;

}

void addEdge(int from,int to) {

end[tot] = to;

nxt[tot] = head[from];

head[from] = tot++;

}

} gph;

int n;

void dfs(int cur,int par) {

gph.par[cur] = par;

gph.siz[cur] = 1;

gph.dp[cur] = 1;

for(int j = gph.head[cur]; j; j = gph.nxt[j]) {

int now = gph.end[j];

if(now != par) {

dfs(now,cur);

gph.siz[cur] += gph.siz[now];

gph.dp[cur] = max(gph.siz[now],gph.dp[cur]);

}

int balance() {

dfs(1,0);

int ret = -1;

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

int dpn = max(gph.dp[i],n-gph.siz[i]);

if(dpn <= n/2) {

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

ret = 0;

}

return ret;

}

int main() {

scanf(" %d",&n);

gph.init();

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

int a,b;

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

gph.addEdge(a,b);

gph.addEdge(b,a);

}

int res = balance();

if(res == -1) {

puts("NONE");

}

return 0;

}

POJ 1655 Balancing Act

December 06, 20152015-12-06hahaschool3 Comments

题意

求树的重心。

思路

树的重心的定义是：选树中某个点i当作树的根，所有子树中最大的那棵的大小是Si，整棵树中能令Si最小的那个点，就是树的重心。

求重心是作为树分治的一个环节出现的，只有保证了每一次点分治的位置都是重心才能保证树分治的复杂度为O(nlogn)。

求重心的想法是树dp，对于每个节点都要存储他所有孩子对应的子树中最大子树的大小，还要存储他的父亲是谁。求好了这些数据之后，按着定义，就可以知道谁是重心了。

代码

#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>
#include <complex>

using namespace std;

const int MAXV = 20005;
const int MAXE = 40005;

struct Graph{
    int siz[MAXV];
    int dp[MAXV];
    int par[MAXV];

    int head[MAXV];
    int nxt[MAXE];
    int end[MAXE];
    int tot;
    void init(){
        memset(head,0,sizeof(head));
        tot = 2;
    }
    void addEdge(int from,int to){
        end[tot] = to;
        nxt[tot] = head[from];
        head[from] = tot++;
    }
} gph;

int n;

void dfs(int cur,int par){
    gph.par[cur] = par;
    gph.siz[cur] = 1;
    gph.dp[cur] = 1;
    for(int j = gph.head[cur]; j; j = gph.nxt[j]){
        int now = gph.end[j];
        if(now != par){
            dfs(now,cur);
            gph.siz[cur] += gph.siz[now];
            gph.dp[cur] = max(gph.siz[now],gph.dp[cur]);
        }
    }
}

int balance(int &mib){
    dfs(1,0);
    int ret = 0;
    mib = 0x3f3f3f3f;
    for(int i = 1; i <= n; i++){
        int dpn = max(gph.dp[i],n-gph.siz[i]);
        if(dpn < mib){
            mib = dpn;
            ret = i;
        }
    }
    return ret;
}



int main(){
    int caseCnt;
    scanf(" %d",&caseCnt);
    for(int d = 1; d <= caseCnt; d++){
        scanf(" %d",&n);
        gph.init();
        for(int i = 1; i < n ; i++){
            int a,b;
            scanf(" %d %d",&a,&b);
            gph.addEdge(a,b);
            gph.addEdge(b,a);
        }
        int mib;
        int res = balance(mib);
        printf("%d %d\n",res,mib);
    }
    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>

#include <complex>

using namespace std;

const int MAXV = 20005;

const int MAXE = 40005;

struct Graph{

int siz[MAXV];

int dp[MAXV];

int par[MAXV];

int head[MAXV];

int nxt[MAXE];

int end[MAXE];

int tot;

void init(){

memset(head,0,sizeof(head));

tot = 2;

}

void addEdge(int from,int to){

end[tot] = to;

nxt[tot] = head[from];

head[from] = tot++;

}

} gph;

int n;

void dfs(int cur,int par){

gph.par[cur] = par;

gph.siz[cur] = 1;

gph.dp[cur] = 1;

for(int j = gph.head[cur]; j; j = gph.nxt[j]){

int now = gph.end[j];

if(now != par){

dfs(now,cur);

gph.siz[cur] += gph.siz[now];

gph.dp[cur] = max(gph.siz[now],gph.dp[cur]);

}

int balance(int &mib){

dfs(1,0);

int ret = 0;

mib = 0x3f3f3f3f;

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

int dpn = max(gph.dp[i],n-gph.siz[i]);

if(dpn < mib){

mib = dpn;

ret = i;

}

return ret;

}

int main(){

int caseCnt;

scanf(" %d",&caseCnt);

for(int d = 1; d <= caseCnt; d++){

scanf(" %d",&n);

gph.init();

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

int a,b;

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

gph.addEdge(a,b);

gph.addEdge(b,a);

}

int mib;

int res = balance(mib);

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

}

return 0;

}

SGU 195 New Year Bonus Grant

July 30, 20152015-07-30hahaschoolLeave a comment

题意

某厂采用一种奇怪的方式发奖金，给出一个上下级关系树，大BOSS是1号根节点，别的员工都有自己的上司。对于每个员工，它有三种选择，要么接受上级下发的奖金，要么给所有下级发奖金，要么啥都不做（只有傻子才会这样，所以你可以当成没这种选择），大BOSS一定发奖金。只要一个员工选择收奖金，他就得到1000块。

现在要你设计一种方案，使得所有人收到的奖金的总数额最大。

思路

树DP解法

对于每一个节点，都有两种状态：选择收奖金，选择收奖金。

对于选择收奖金的节点的儿子节点，一定不可以选择收奖金。

对于选择发奖金的节点的儿子节点，可以选择收他的奖金，也可以选择发奖金。

这样就可以建立dp数组dp[a][0/1]，a是节点对应的编号，0/1表示该节点选择收／发奖金的状态。利用DFS下潜到叶子节点之后，就可以开始树DP了。

状态转移的方程可以参考dfs()方法。

输出路径的话，只要记录下每一次的决策，DP结束之后反查就可以搞定。

贪心解法

引用自JHC23的Blog。

自底而顶遍历，如果自己的上级没有接受奖金（那么就能够把钱给发自己了），而自己也从不增接受奖金则可以获得奖金，同时标记自己和上级。这样下去就可以得到可得到最大奖金。

代码

树DP解法：

//
//  SGU195.cpp
//  playground
//
//  Created by Adam Chang on 2015/07/29.
//  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 nodeType{
    vector<int> to;
    int select;
} vertex[500005];

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

int dp[500005][2];
void dfs(int cur){
    nodeType &currNode = vertex[cur];
    for (int i = 0; i < currNode.to.size(); i++) {
        dfs(currNode.to[i]);
    }
    for (int i = 0; i < currNode.to.size(); i++) {
        if (dp[cur][0]+dp[currNode.to[i]][0]+1>= max(dp[cur][1]+dp[currNode.to[i]][1],dp[cur][1]+dp[currNode.to[i]][0])) {
            currNode.select = currNode.to[i];
        }
        dp[cur][1] = max(dp[cur][0]+dp[currNode.to[i]][0]+1, max(dp[cur][1]+dp[currNode.to[i]][1],dp[cur][1]+dp[currNode.to[i]][0]));
        dp[cur][0] = max(dp[cur][0]+dp[currNode.to[i]][1],dp[cur][0]+dp[currNode.to[i]][0]);
    }
}

vector<int> ans;
void dfs_getans(int cur){
    nodeType &currNode = vertex[cur];
    if (dp[cur][0] >= dp[cur][1]) {
        for (int i = 0; i < currNode.to.size(); i++) {
            dfs_getans(currNode.to[i]);
        }
    }else{
        if (currNode.select) {
            ans.push_back(currNode.select);
        }
        for (int i = 0; i < currNode.to.size(); i++) {
            dfs_getans(currNode.to[i]);
        }
    }
}

int main(){
    int n = 0;
    scanf(" %d",&n);
    for (int i = 1; i <= n; i++) {
        vertex[i].to.clear();
        vertex[i].select = 0;
        dp[i][0] = dp[i][1] = 0;
    }
    ans.clear();
    for (int i = 2; i <= n; i++) {
        int boss = 0;
        scanf(" %d",&boss);
        addEdge(boss,i);
    }
    dfs(1);
    dfs_getans(1);
    sort(ans.begin(), ans.end());
    cerr << dp[1][0] << " " << dp[1][1] << endl;
    printf("%d\n",(int)ans.size()*1000);
    if (ans.size()) {
        for (int i = 0; i < (int)ans.size()-1; i++) {
            printf("%d ",ans[i]);
        }
        printf("%d\n",ans[ans.size()-1]);
    }
    return 0;
}

// SGU195.cpp

// playground

// Created by Adam Chang on 2015/07/29.

#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 nodeType{

vector<int> to;

int select;

} vertex[500005];

void addEdge(int from,int to){

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

}

int dp[500005][2];

void dfs(int cur){

nodeType &currNode = vertex[cur];

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

dfs(currNode.to[i]);

}

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

if (dp[cur][0]+dp[currNode.to[i]][0]+1>= max(dp[cur][1]+dp[currNode.to[i]][1],dp[cur][1]+dp[currNode.to[i]][0])) {

currNode.select = currNode.to[i];

}

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

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

}

vector<int> ans;

void dfs_getans(int cur){

nodeType &currNode = vertex[cur];

if (dp[cur][0] >= dp[cur][1]) {

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

dfs_getans(currNode.to[i]);

}

}else{

if (currNode.select) {

ans.push_back(currNode.select);

}

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

dfs_getans(currNode.to[i]);

}

int main(){

int n = 0;

scanf(" %d",&n);

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

vertex[i].to.clear();

vertex[i].select = 0;

dp[i][0] = dp[i][1] = 0;

}

ans.clear();

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

int boss = 0;

scanf(" %d",&boss);

addEdge(boss,i);

}

dfs(1);

dfs_getans(1);

sort(ans.begin(), ans.end());

cerr << dp[1][0] << " " << dp[1][1] << endl;

printf("%d\n",(int)ans.size()*1000);

if (ans.size()) {

for (int i = 0; i < (int)ans.size()-1; i++) {

printf("%d ",ans[i]);

}

printf("%d\n",ans[ans.size()-1]);

}

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;

}

Codeforces 461B Appleman and Tree

July 29, 20152015-07-29hahaschoolLeave a comment

题意

给你一颗树，上面有黑色节点，也有白色节点，现在你要做的事情是，在这棵树上选出几条边，去掉，这样的话这棵树就会变成好多小树，这些小树一定要含且只含一个黑色点。问你有多少种不同的方法删边来满足要求。

思路

树形DP。往DP方面去想是因为原始的大问题可以进行剖分，即如果我们想要知道将整棵树按要求切割的方案个数，我们可以去考虑它的子树按要求切割的方案个数，对于子树也是同样地进行剖分。确定了将问题剖分的方向之后，就是确定状态了。

我们发现，要想从一颗树的子树的分割情况得到整棵树的分割情况，我们不仅要知道子树符合要求的分割情况，也要知道子树不符合要求的分割情况，这样才能覆盖全部情况。因此我们设定状态为 $dp[a][0/1]$ ，其中 $dp[a][0]$ 存值为将以 $a$ 为根节点的子树进行分割，而且与当前的子树根节点相连的节点中没有黑色节点方法个数； $dp[a][1]$ 存值为将以 $a$ 为根节点的子树进行分割，而且与当前的子树根节点相连的节点中有且仅有一个黑色节点方法个数。

这里一定要清楚，0/1表示的是与根节点联通的节点中是不是有黑色的节点，已经断开的地方，我们不用关心。

接下来讨论状态的转移：

如果当前节点已经是叶子节点，节点编号是：
- 如果是黑色节点：
  - $dp[a][0] = 0$ 因为黑色节点为根部的子树不可能不含有黑色节点。
  - $dp[a][1] = 1$ 因为只有黑色节点一个点，只有一种分割方式就是把节点自己当作一颗树。
- 如果是白色节点：
  - $dp[a][0] = 1$ 因为白色叶子节点的子树中只有他自己一个白色节点，不可能含有黑色节点了，分割方式也只有一种就是把自己当成子树。
  - $dp[a][1] = 0$ 因为白色叶子节点的子树中不可能含有黑色节点。
如果当前节点不是叶子节点，节点编号是，它的孩子节点们的编号为b_{i}：
- 如果是白色节点：
  - ，我们逐一检查每一个孩子节点，我们想得到的结果是当前节点直接相连的联通块里面不存在黑色节点，那么：
    - 如果当前检查的孩子节点是黑色的，我们考虑切开还是不切开同这个孩子节点连接的边：
      - 不切开的话，要求连接的孩子部分一定不可以有黑色节点，这显然是不可能的，不过黑色节点的 $dp[a][0] = 0$ 始终是0，所以没关系。
      - 切开的话，就要求切开之后的孩子部分自己可以满足要求，这样的话有 $dp[b_{i}][1]$ 种方法。
    - 如果当前检查的孩子节点是白色的，我们考虑切开／不切开同孩子连接的边：
      - 切开的话，孩子部分自己要满足要求，这样的话有 $dp[b_{i}][1]$ 种方法。
      - 不切开的话，孩子部分与根节点直接相连的部分一定不可以包含黑色节点，这样的话有 $dp[b_{i}][0]$ 种方法。
  - ，这个方程的计算必须和上面的同步进行。这个有一点不好懂，其实可以这么想：
    - $dp[a][1]*(dp[b_{i}][0]+dp[b_{i}][1])$ 这一部分，我们要想的过程是将一个已经连接好了黑点的根部，讨论是不是要和当前的孩子相连的过程：
    - 如果当前检查的节点是黑色节点，我们还是考虑切开／不切开：
      - 不切开的话不满足要求，不过黑色节点的 $dp[a][0] = 0$ 始终是0，所以没关系。
      - 切开的话，连接上去的孩子部分一定要满足要求，有且只有一个黑点，所以有 $dp[b_{i}][1]$ 种方法。
    - 如果当前检查的是白色节点，切开／不切开：
      - 不切开的话，还是不满足要求，但是如果这个时候在根节点上已经有带黑点的联通块连上去了，这个时候只要令连接上去的部分没有黑点就可以了，所以有 $dp[b_{i}][0]$ 种方法。
      - 切开的话，孩子部分要自己保持成立，有且只有一个黑点，所以有 $dp[b_{i}][1]$ 种方法。
    - 而 $dp[a][0]*dp[b_{i}][1]$ 这一部分，想法是当前依然不成立的根部，和带有一个黑点的孩子部分连接。
- 如果是黑色节点：
  - $dp[a][0] = 0$ 因为黑色节点为根部的子树不可能不含有黑色节点
  - 我们逐一检查每一个孩子节点，既然我们想得到的结果是当前节点直接相连的联通块里面只有一个黑色节点，那么：
    - 如果当前检查的孩子节点是黑色的，我们考虑切开还是不切开同这个孩子节点连接的边：
      - 切开的话，没有问题，因为当前考虑的子树的根节点已经是黑的了，而且还要让让切开之后切出来的孩子的那一部分保持成立，要想做到这一点的话有 $dp[b_{i}][1]$ 种方法。
      - 不切开的话，显然是不行的，因为这样就有了两个黑色节点，不过黑色节点的 $dp[a][0] = 0$ 始终是0，所以加进去也没关系。
    - 如果当前检查的孩子节点是白色的，我们考虑切开／不切开同孩子连接的边：
      - 切开的话，还要保证切除的孩子部分也成立，因此孩子部分有 $dp[b_{i}][1]$ 种方法。
      - 不切开的话，因为当前节点是黑色的，链接孩子节点之后，连接上的部分不可以含有黑色节点，孩子节点能做到这样的方法有 $dp[b_{i}][0]$ 种。

写了一堆废话其实就是为了理清思路，思维能力太弱只能这样了。DP的思路搞定之后，具体的操作就非常简单，利用DFS深入叶子，在返回的过程中进行对孩子的考察和对自身的更新，最后在根节点上读取答案。

代码

//
//  CF461B.cpp
//  playground
//
//  Created by Adam Chang on 2015/07/29.
//  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;

static long long MODER = 1000000007;

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

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

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] = 0;
        dp[cur][1] = 1;
        for (int i = 0; i < currNode.to.size(); i++) {
            if (currNode.to[i] != par) {
                dp[cur][1] *= dp[currNode.to[i]][0] + dp[currNode.to[i]][1];
                dp[cur][1] %= MODER;
            }
        }
    }else {
        dp[cur][0] = 1;
        dp[cur][1] = 0;
        for (int i = 0; i < currNode.to.size(); i++) {
            if (currNode.to[i] != par) {
                dp[cur][1] = dp[cur][0] * dp[currNode.to[i]][1] + dp[cur][1] * (dp[currNode.to[i]][0] + dp[currNode.to[i]][1]);
                dp[cur][1] %= MODER;
                dp[cur][0] *= dp[currNode.to[i]][0] + dp[currNode.to[i]][1];
                dp[cur][0] %= MODER;
            }
        }
    }
}

int main(){
    int n = 0;
    scanf(" %d",&n);
    for (int i = 0; i < n; i++) {
        vertex[i].to.clear();
    }
    for (int i = 1; i < n; i++) {
        int to;
        scanf(" %d",&to);
        addEdge(i, to);
        addEdge(to, i);
    }
    for (int i = 0; i < n; i++) {
        scanf(" %d",&vertex[i].color);
    }
    dfs(0,-1);
    cout << (dp[0][1] + MODER) % MODER << endl;
    return 0;
}

// CF461B.cpp

// playground

// Created by Adam Chang on 2015/07/29.

#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 MODER = 1000000007;

struct nodeType{

vector<int> to;

int color;

} vertex[100005];

void addEdge(int from,int to){

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

}

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] = 0;

dp[cur][1] = 1;

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

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

dp[cur][1] *= dp[currNode.to[i]][0] + dp[currNode.to[i]][1];

dp[cur][1] %= MODER;

}

}else {

dp[cur][0] = 1;

dp[cur][1] = 0;

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

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

dp[cur][1] = dp[cur][0] * dp[currNode.to[i]][1] + dp[cur][1] * (dp[currNode.to[i]][0] + dp[currNode.to[i]][1]);

dp[cur][1] %= MODER;

dp[cur][0] *= dp[currNode.to[i]][0] + dp[currNode.to[i]][1];

dp[cur][0] %= MODER;

}

int main(){

int n = 0;

scanf(" %d",&n);

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

vertex[i].to.clear();

}

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

int to;

scanf(" %d",&to);

addEdge(i, to);

addEdge(to, i);

}

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

scanf(" %d",&vertex[i].color);

}

dfs(0,-1);

cout << (dp[0][1] + MODER) % MODER << endl;

return 0;

}

HDU 4035 Maze

April 06, 20152015-04-06hahaschoolLeave a comment

题意

一个人被丢进了迷宫，迷宫有n个房间，1号房间作为起点，房间之间以隧道联通，任意两个房间的通路只有一条，每进入一个房间，有k的概率被干掉，然后在1号房间复活，有e的概率直接脱出迷宫，若上述两事件未发生，则这个人会从当前房间的全部隧道中随便选一个进去（即使沿着刚才的路返回）。问你这个人要穿过多少隧道才能拖出迷宫（求期望）。

思路

注意审题，“任意两个房间的通路只有一条” ，这句话告诉我们迷宫可以抽象为一棵树（因为没有环，起点确定所以看作树根），又因为是求期望，所以这是一个树上进行的概率dp。
对于每个节点，我们定义dp数组为dp[i]表示在i号房间脱出迷宫的期望穿洞数。
接下来就是处理dp方程，如果你可以写出来dp方程的话，你会发现这个方程有两种版本，一种是叶子节点，一种是普通节点（其实还有一种根节点，不过这个只是最后出答案用的），列完之后我们会发现dp方程组成环，而且每一个方程式都有着类似的未知项（或者说是格式统一），面对这种情况就可以归纳出方程的一般形式，建立几个系数数组，回代一般形式，确定出系数数组的递推关系式，化环为链。这种情形经常出现在概率dp问题中。
最后需要注意本题有坑点：判断误解的时候，需要直接判断1-A[1](这个是什么请看下面的数学推导）的绝对值是否非常小（分母趋向于0），在这里卡精度，你至少需要1e-9的精度。在这里用其他的方法判断一律是过不了的～

代码

//
//  HDU4035.cpp
//  playground
//
//  Created by Adam Chang on 2015/4/5.
//  Copyright (c) 2015年 Adam Chang. All rights reserved.
//
//Review: Each pair of rooms is connected by one and only one path
//this statement marks the structure is tree (or DAG),i.e. no rings.

#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 vertexType{
    vector<int> to;
    double pk,pe;
    void init(){
        to.clear();
        pk = 0;
        pe = 0;
    }
} vertex[10005];

double A[10005],B[10005],C[10005];
bool vis[10005];
void dfs(int father){
    vis[father] = true;
    vector<int> child;
    for (int i = 0; i < vertex[father].to.size(); i++) {
        int next = vertex[father].to[i];
        if (vis[next]) {
            continue;
        }
        child.push_back(next);
        dfs(next);
    }

    double w = 1-vertex[father].pk-vertex[father].pe;
    if (child.size()) {
        //normal vertex
        double m = (double)vertex[father].to.size();
        double q = 1;
        double e = vertex[father].pk;
        double r = w;
        for (int i = 0; i < child.size(); i++) {
            e += w/m*A[child[i]];
            q -= w/m*B[child[i]];
            r += w/m*C[child[i]];
        }
        A[father] = e/q;
        B[father] = w/m/q;
        C[father] = r/q;
    }else{
        //endpoint vertex
        A[father] = vertex[father].pk;
        B[father] = w;
        C[father] = w;
    }
}


int main(){
    int caseCnt;
    scanf(" %d",&caseCnt);
    for (int ci = 1; ci <= caseCnt; ci++) {
        int n = 0;
        scanf(" %d",&n);
        for (int i = 1; i <= n; i++) {
            vertex[i].init();
        }
        for (int i = 1; i <= n-1; i++) {
            int arg1,arg2;
            scanf(" %d %d",&arg1,&arg2);
            vertex[arg1].to.push_back(arg2);
            vertex[arg2].to.push_back(arg1);
        }
        for (int i = 1; i <= n; i++) {
            double arg1,arg2;
            scanf(" %lf %lf",&arg1,&arg2);
            vertex[i].pk = arg1/100;
            vertex[i].pe = arg2/100;
        }
        memset(A, 0, sizeof(A));
        memset(B, 0, sizeof(B));
        memset(C, 0, sizeof(C));
        memset(vis, 0, sizeof(vis));
        dfs(1);
        if (abs(1-A[1]) < 0.000000001) {//这里卡精度
            printf("Case %d: impossible\n",ci);
            continue;
        }
        printf("Case %d: %.10lf\n",ci,C[1]/(1-A[1]));
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

// HDU4035.cpp

// playground

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

//Review: Each pair of rooms is connected by one and only one path

//this statement marks the structure is tree (or DAG),i.e. no rings.

#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 vertexType{

vector<int> to;

double pk,pe;

void init(){

to.clear();

pk = 0;

pe = 0;

}

} vertex[10005];

double A[10005],B[10005],C[10005];

bool vis[10005];

void dfs(int father){

vis[father] = true;

vector<int> child;

for (int i = 0; i < vertex[father].to.size(); i++) {

int next = vertex[father].to[i];

if (vis[next]) {

continue;

}

child.push_back(next);

dfs(next);

}

double w = 1-vertex[father].pk-vertex[father].pe;

if (child.size()) {

//normal vertex

double m = (double)vertex[father].to.size();

double q = 1;

double e = vertex[father].pk;

double r = w;

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

e += w/m*A[child[i]];

q -= w/m*B[child[i]];

r += w/m*C[child[i]];

}

A[father] = e/q;

B[father] = w/m/q;

C[father] = r/q;

}else{

//endpoint vertex

A[father] = vertex[father].pk;

B[father] = w;

C[father] = w;

}

int main(){

int caseCnt;

scanf(" %d",&caseCnt);

for (int ci = 1; ci <= caseCnt; ci++) {

int n = 0;

scanf(" %d",&n);

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

vertex[i].init();

}

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

int arg1,arg2;

scanf(" %d %d",&arg1,&arg2);

vertex[arg1].to.push_back(arg2);

vertex[arg2].to.push_back(arg1);

}

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

double arg1,arg2;

scanf(" %lf %lf",&arg1,&arg2);

vertex[i].pk = arg1/100;

vertex[i].pe = arg2/100;

}

memset(A, 0, sizeof(A));

memset(B, 0, sizeof(B));

memset(C, 0, sizeof(C));

memset(vis, 0, sizeof(vis));

dfs(1);

if (abs(1-A[1]) < 0.000000001) {//这里卡精度

printf("Case %d: impossible\n",ci);

continue;

}

printf("Case %d: %.10lf\n",ci,C[1]/(1-A[1]));

}

return 0;

}

Tag: 树DP

POJ 2114 Boatherds

题意

思路

代码

POJ 1987 Distance Statistics

题意

思路

代码

POJ 3107 Godfather

题意

思路

代码

POJ 2378 Tree Cutting

题意

思路

代码

POJ 1655 Balancing Act

题意

思路

代码

SGU 195 New Year Bonus Grant

题意

思路

树DP解法

贪心解法

代码

HDU 4313 Matrix

题意

思路

代码

Codeforces 461B Appleman and Tree

题意

思路

代码

HDU 4035 Maze

题意

思路

相关数学推导

代码