ACdream 1119 瑶瑶的动感光波（加强版）(LCA)（背包dp）

妖狐艹你老母 2022-06-12 02:06 195阅读 0赞

题目链接：  
[ACdream 1109][]

题意：中文题意….

题解：  
如果这题按照 [ACdream 1102 题解][ACdream 1102] 去做，肯定会TLE。

我们先DFS 预处理出全部结点的父节点，深度所有点对的LCA （最近公共祖先）。枚举以每个结点开始到根结点这段路径上每一段长度上背包容量为0 ~50 的选取情况的最优价值。对于每次询问，可以拆分成两部分，一部分是x 到z 且包括z 的一段路径，即：dep\[x\]−dep\[z\]\+1 。另一部分是y 到 LCA（x，y）  且不包括 LCA（x，y）  的路径，即dep\[y\]−dep\[Fa\]，Fa=LCA(x,y) 。然后对每条路做一次背包，然后再对得到的背包中选取最优值即可。

详细可以看代码。

AC代码：

/*
    * this code is made by LzyRapx
    * Problem: 1119
    * Verdict: Accepted
    * Submission Date: 2017-07-12 18:56:39
    * Time: 1448MS
    * Memory: 46500KB
    */
    #include<bits/stdc++.h>
    using namespace std;
    const int maxn = 12345;
    int tree[maxn],nxt[maxn],head[maxn],all;
    int a[maxn],b[maxn];
    
    void addedge(int u,int v)
    {
        tree[all] = v; nxt[all] = head[u]; head[u] = all++;
        tree[all] = u; nxt[all] = head[v]; head[v] = all++; 
    }
    int fa[maxn][15];
    int dep[maxn];
    
    struct Seg
    {
        int dp[55];
        void init( int u, int v )
        {
            memset(dp, -1, sizeof(dp)); 
            dp[0] = 0;
            dp[u] = v;
        }
        Seg operator + (const Seg &a ) const
        {
            Seg b;
            for(int i=0;i<=50;i++) 
            {
                b.dp[i] = a.dp[i];
            }
            for(int i=0;i<=50; i++) 
            {
                if(dp[i]>=0)
                {
                    for(int j = 50-i; j >= 0; --j) 
                    {
                        if(a.dp[j]>=0)
                        {
                            b.dp[j+i] = max(b.dp[i+j], dp[i] + a.dp[j]);
                        }
    
                    }
                }
            }
            return b;
        }
    }sg[maxn][15], gg[maxn];
    
    void dfs(int u,int Fa)
    {
        dep[u] = dep[Fa] + 1;
        sg[u][0].init(a[u],b[u]);
        gg[u].init(a[u],b[u]);
        Seg tmp;
        for(int i=0;fa[u][i];i++)
        {
            fa[u][i+1] = fa[fa[u][i]][i];
            sg[u][i+1] = sg[u][i] + sg[fa[u][i]][i];
        }
        for(int i = head[u]; i+1; i = nxt[i])
        {
            int v = tree[i];
    
            if(v==Fa)continue;
    
            fa[v][0] = u;
            dfs(v,u);
            tmp.init(a[u],b[u]);
            tmp = tmp + gg[v];
            for(int j=0;j<=50;j++)
            {
                gg[u].dp[j] = max(gg[u].dp[j],tmp.dp[j]);
            }
        }
    }
    int UP(int u,int d)
    {
        for(int i = 0 ; d ; i++)
        {
            if((d>>i) & 1)
            {
                u = fa[u][i];
                d -= 1<<i;  
            }
        }
        return u;
    }
    int LCA(int u,int v)
    {
        if(dep[v] > dep[u]){
            swap(u,v);
        }
        u = UP(u, dep[u] - dep[v]);
        if(u == v) return u;
        for(int i=14;i>=0;--i)
        {
            if(fa[u][i] - fa[v][i])
            {
                u = fa[u][i];
                v = fa[v][i];
            }
        }
        return fa[u][0];
    }
    Seg sgJump(int u,int d)
    {
        Seg b;
        b.init(0,0);
        for(int i=0;d;i++)
        {
            if((d>>i) & 1)
            {
                b = b + sg[u][i];
                u = fa[u][i];
                d -= 1<<i;  
            }
        }
        return b;
    }
    int solve(int z,int x,int y,int w)
    {
        Seg b;
        b.init(0,0);
        if(dep[y] > dep[x]){
            swap(x,y);
        }
        int Fa = LCA(x,y);
        b = b + sgJump(x,dep[x] - dep[z] + 1);
        b = b + sgJump(y,dep[y] - dep[Fa]);
        int ans = 0;
        for(int i=0;i<=w;i++)
        {
            ans = max(ans,b.dp[i]); 
        } 
        return ans ;
    }
    int main()
    {
        int u,v,n,m,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",&u,&v);
                addedge(u,v);
            }
            dfs(1,0);
            while(m--)
            {
                scanf("%d%d%d%d",&z,&x,&y,&w);
                int ans = solve(z,x,y,w);
                printf("%d\n",ans);
            }
        }
        return 0;
    }

[ACdream 1109]: http://acdream.info/problem?pid=1119
[ACdream 1102]: http://blog.csdn.net/liangzhaoyang1/article/details/74911214