CCPC-Wannafly Winter Camp Day1 流流流动（树形dp）-白红宇

输入描述

第一行一个整数

接下来一行

$\leq n \leq 1001≤n≤100$

$\leq f[i], d[i] \leq 10001≤f[i],d[i]≤1000$

输出描述

输出一个整数表示答案。

样例输入 1

210 10 1 2

样例输出 1

19 思路： 根据题目给的建边条件，建边后会形成一个森林，然后把森林转化为一个0为根节点的树，随后进行树形dp。 定义状态： dp[u][0/1]  0为 第u个节点的子树中不取第u个节点的最多利益值， 　　　　　　　1为第u个节点的子树中取第u个节点的最多利益值， 常规的树形dp套路， dp[u][0]+=max(dp[v][0],dp[v][1]); dp[u][1]+=max(dp[v][0],dp[v][1]-d[min(u,v)]);// 一个边上两个节点都取的话，要减去对应的值。 最后max(dp[0][0],dp[0][1])就是我们的答案值。 细节见代码：

#include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  #include 
                  
                   #include 
                   #include 
                    
                     #include 
                     
                      #include 
                      
                       #define ALL(x) (x).begin(), (x).end()#define rt return#define dll(x) scanf("%I64d",&x)#define xll(x) printf("%I64d\n",x)#define sz(a) int(a.size())#define all(a) a.begin(), a.end()#define rep(i,x,n) for(int i=x;i
                       
                        #define pll pair
                        
                         #define gbtb ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)#define MS0(X) memset((X), 0, sizeof((X)))#define MSC0(X) memset((X), '\0', sizeof((X)))#define pb push_back#define mp make_pair#define fi first#define se second#define eps 1e-6#define gg(x) getInt(&x)#define db(x) cout<<"== [ "<
                         
                          <<" ] =="<

v[maxn];int w;void dfs(int u, int pre){ // cout<

<<" "<

<
                             
                              > n;    repd(i, 1, n)    {        cin >> f[i];    }    repd(i, 1, n)    {        cin >> d[i];    }    repd(i, 2, n)    {        if (i & 1)        {            if (3 * i + 1 <= n)            {                v[i].push_back(3 * i + 1);                v[3 * i + 1].push_back(i);                mer(i, 3 * i + 1);            }        } else        {            v[i].push_back(i / 2);            v[i / 2].push_back(i);            mer(i, i / 2);        }    }    repd(i, 1, n)    {        if (pre[i] == 0)        {            v[0].push_back(i);            v[i].push_back(0);        }    }    dfs(0, 0);    cout << max(dp[0][0], dp[0][1]) << endl;    return 0;}inline void getInt(int* p) {    char ch;    do {        ch = getchar();    } while (ch == ' ' || ch == '\n');    if (ch == '-') {        *p = -(getchar() - '0');        while ((ch = getchar()) >= '0' && ch <= '9') {            *p = *p * 10 - ch + '0';        }    }    else {        *p = ch - '0';        while ((ch = getchar()) >= '0' && ch <= '9') {            *p = *p * 10 + ch - '0';        }    }}