ACdream 1102 瑶瑶的动感光波（树形dp）（背包dp）

分手后的思念是犯贱 2022-06-11 23:45 145阅读 0赞

题目链接：  
[ACdream 1102 ][ACdream 1102]

题意：  
自己点链接进去看吧…中文题面。。。

![这里写图片描述][T4.png]

题解：  
先预处理求出每个结点的父节点，然后在这棵树上做背包 dp  就可以了。

这题还有加强版。  
题目链接：  
[ACdream 1119][]  
加强版题解：  
[ACdream 1119 题解][ACdream 1119 1]

做法有点复杂。这题代码交上去完全会TLE。

等等写一下加强版吧。

AC代码：

/*
    * this code is made by LzyRapx
    * Problem: 1102
    * Verdict: Accepted
    * Submission Date: 2017-07-10 11:53:04
    * Time: 4MS
    * Memory: 2056KB
    */
    #include<bits/stdc++.h>
    using namespace std;
    struct edge{
        int nxt,y;
    }tree[30005];
    int n,m;
    int all;
    int dp[105];
    int head[30005];
    bool vis[3005];
    int a[3005],b[3005],fa[3005];
    void addedge(int x,int y)
    {
        tree[all].nxt = head[x];
        tree[all].y = y;
        head[x] = all++;
    }
    void pre(int x,int p)
    {
        fa[x] = p;
        for(int i=head[x];i!=-1;i=tree[i].nxt)
        {
            if(tree[i].y == p) continue;
            pre(tree[i].y,x);
        }
    }
    void dfs(int x,int z,int w)
    {
        if(vis[x]==true)return;
        vis[x] = true;
        for(int i=w;i>=a[x];--i)
        {
            dp[i] = max(dp[i],dp[i-a[x]] + b[x]);
        }
        if(x==z)return;
        dfs(fa[x],z,w);
    }
    int main()
    {
        int x,y,z,w;
        while(~scanf("%d%d",&n,&m))
        {
            memset(head,-1,sizeof(head));
            all = 0;
            for(int i=1;i<=n;i++){
                scanf("%d%d",&a[i],&b[i]);
            }
            for(int i=1;i<n;i++){
                scanf("%d%d",&x,&y);
                addedge(x,y);
                addedge(y,x);
            }
            pre(1,-1);
            while(m--)
            {
                scanf("%d%d%d%d",&z,&x,&y,&w);
                memset(vis,false,sizeof(vis));
                memset(dp,0,sizeof(dp));
                dfs(x,z,w);
                dfs(y,z,w);
                printf("%d\n",dp[w]);   
            } 
        }
        return 0;
     }

[ACdream 1102]: http://acdream.info/problem?pid=1102
[T4.png]: http://acdream.info/img/prob/1102/T4.png
[ACdream 1119]: http://acdream.info/problem?pid=1119
[ACdream 1119 1]: http://blog.csdn.net/liangzhaoyang1/article/details/75040197