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

题目链接：

​​​ACdream 1109​​

题意：中文题意….

题解：

如果这题按照 ​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) 。然后对每条路做一次背包，然后再对得到的背包中选取最优值即可。

/*
* 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;
}