狂三來襲

· · 题解

没啥意味题（除了题面，因为：）

他甚至使用嘴遁使得 Samcompu 不得不在自己的網站上掛上時崎狂三。

给定一颗 n 个点的树，有 m 个点有值，经过一个点可以得到相应的值，重复经过不多次贡献。边有边权，你需要从根开始走，经过总边权不超过 tim，使得到的值尽量多。

做法：

首先边权乘 2，问题变为选择一个包含根的连通块。

注意到 m 特别小，于是对其建虚树。

然后做一个树上背包，枚举是否走到每个儿子即可。复杂度为 O(2 \times m \times tim)。

最后预处理答案的前缀和就做完了，注意 sub2 和 sub3 的数据范围量级不同。

这里贴下代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,q,tot,num,f[N],d[N],siz[N],son[N],top[N],id[N],len[N],vt[N],vis[N],op;
vector<pair<int,int> > e[N];
int dfs1(int u,int fa,int dep){f[u]=fa,d[u]=dep,siz[u]=1;int maxn=-1;for(auto it:e[u]){int v=it.first;if(v==fa) continue;len[v]=len[u]+it.second;siz[u]+=dfs1(v,u,dep+1);if(siz[v]>maxn) maxn=siz[v],son[u]=v;}return siz[u];}
void dfs2(int u,int t){top[u]=t,id[u]=++tot;if(!son[u]) return;dfs2(son[u],t);for(auto v:e[u])if(!id[v.first]) dfs2(v.first,v.first);}
int LCA(int x,int y){while(top[x]!=top[y]){if(d[top[x]]<d[top[y]]) swap(x,y);x=f[top[x]];}return d[x]<d[y]?x:y;}
bool cmp(int x,int y){return id[x]<id[y];}
int f1[45][N],f2[205][105],s[N],tott;
struct TOKISAKI_KURUMI{
    int cnt,siz[N];
    vector<int> g[N];
    void tree_dp(int x){
        s[x]=++tott,siz[x]=0;
        if(op){
            if(vis[x]) f1[s[x]][0]=vis[x];
            for(auto v:g[x]){
                tree_dp(v);int w=len[v]-len[x];
                for(int i=min(N-1,siz[x]+siz[v]+w);i>=0;i--)
                    for(int j=0;j<=min(i-w,siz[x]);j++)
                        f1[s[x]][i]=max(f1[s[x]][i],f1[s[x]][j]+f1[s[v]][i-w-j]);
                siz[x]+=siz[v]+w;
            }
        }
        else{
            if(vis[x]) f2[s[x]][0]=vis[x];
            for(auto v:g[x]){
                tree_dp(v);int w=len[v]-len[x];
                for(int i=min(104,siz[x]+siz[v]+w);i>=0;i--)
                    for(int j=0;j<=min(i-w,siz[x]);j++)
                        f2[s[x]][i]=max(f2[s[x]][i],f2[s[x]][j]+f2[s[v]][i-w-j]);
                siz[x]+=siz[v]+w;
            }
        }
    }
    void work(){
        tot=0,cnt=num;
        sort(vt+1,vt+cnt+1,cmp);
        for(int i=2;i<=num;i++) vt[++cnt]=LCA(vt[i-1],vt[i]);
        sort(vt+1,vt+cnt+1,cmp);
        cnt=unique(vt+1,vt+cnt+1)-vt-1;
        for(int i=2;i<=cnt;i++) g[LCA(vt[i-1],vt[i])].push_back(vt[i]);
        tree_dp(vt[1]);
        if(op){
            for(int i=1;i<N;i++) f1[s[vt[1]]][i]=max(f1[s[vt[1]]][i],f1[s[vt[1]]][i-1]);
        }
        else{
            for(int i=1;i<105;i++) f2[s[vt[1]]][i]=max(f2[s[vt[1]]][i],f2[s[vt[1]]][i-1]);
        }
    }
}aya;
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>num>>q;
    op=(num<=20);
    for(int i=1,u,v,w;i<n;i++){
        cin>>u>>v>>w;w<<=1;
        e[u].push_back({v,w});
        e[v].push_back({u,w});
    }
    dfs1(1,0,1),dfs2(1,1);
    for(int i=1,x;i<=num;i++) cin>>vt[i]>>x,vis[vt[i]]=x;
    aya.work();
    while(q--){
        int x;cin>>x;
        cout<<(op?f1[s[vt[1]]][x]:f2[s[vt[1]]][x])<<'\n';
    }
    return 0;
}

好了题解结束，谢谢观看。