題意省略。
分析：對于每個詢問，其實我們把樹上的dfs序求出來，然後每次的詢問其實就是去掉其中的一段區間。那麼我們可以維護一下這個區間的dp字首和字尾，然後詢問的時候合并一下就好了。
怎麼合并：
考慮到這個背包如果把轉移不到的位置去掉，那麼剩下部分就是單調遞增的（就算不單調遞增也可以讓他強行單調遞增），那麼就可以用雙指針來維護啦。
注意詢問要按照左端點排序，然後字首和滾動，不然兩個加在一起空間會GG。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
const int N=+;
int n,m,ban,tot,cnt,now;
typedef long long ll;
const ll inf=;
ll f[*];
ll g[][*];
struct node
{
int t;
ll b;
int id;
}Q[N];
int answ[N];
int v[N],c[N];
int head[N],next[N],go[N],dfn[N],sum[N];
int a[N];
int Left[N],Right[N];
inline void add(int x,int y)
{
go[++tot]=y;
next[tot]=head[x];
head[x]=tot;
}
int tim=;
bool cmp(node a,node b)
{
return Left[a.t]<Left[b.t];
}
inline void dfs(int x,int fa)
{
dfn[x]=++tim;
a[tim]=x;
Left[x]=Right[x]=dfn[x];
for(int i=head[x];i;i=next[i])
{
int v=go[i];
if (v!=fa)
{
dfs(v,x);
}
}
Right[x]=tim;
}
inline void cal(int lim)
{
fo(i,now+,lim)
{
int x=a[i];
int m=sum[i];
fd(j,m,v[x])
{
if (j-v[x]==||f[j-v[x]])
{
if (!f[j])f[j]=f[j-v[x]]+c[x];
else f[j]=min(f[j],f[j-v[x]]+c[x]);
}
}
ll mn=inf;
fd(j,m,)
if (f[j])
{
if (f[j]>=mn)f[j]=;
else mn=min(mn,f[j]);
}
}
now=lim;
}
int main()
{
freopen("plan.in","r",stdin);
freopen("plan.out","w",stdout);
scanf("%d",&n);
fo(i,,n-)
{
int x,y;
scanf("%d%d",&x,&y);
add(x,y);
add(y,x);
}
fo(i,,n)scanf("%d%d",&v[i],&c[i]);
dfs(,);
fo(i,,n)sum[i]=sum[i-]+v[a[i]];
fd(i,n,)
{
int x=a[i],m=sum[n]-sum[i-];
fo(j,,v[x]-)g[i][j]=g[i+][j];
fo(j,v[x],m)
{
g[i][j]=g[i+][j];
if (j-v[x]==||g[i+][j-v[x]])
{
if (!g[i][j])g[i][j]=g[i+][j-v[x]]+c[x];
else g[i][j]=min(g[i][j],g[i+][j-v[x]]+c[x]);
}
}
ll mn=inf;
fd(j,m,)
if (g[i][j])
{
if (g[i][j]>=mn)g[i][j]=;
else mn=min(mn,g[i][j]);
}
}
int q;
scanf("%d",&q);
fo(i,,q)scanf("%d%lld",&Q[i].t,&Q[i].b),Q[i].id=i;
sort(Q+,Q++q,cmp);
fo(i,,q)
{
if (Left[Q[i-].t]-!=Left[Q[i].t]-)cal(Left[Q[i].t]-);
ll b=Q[i].b;
int id=Q[i].id;
int l=Left[Q[i].t]-;
int r=Right[Q[i].t]+;
int pre=sum[n]-sum[r-]+;
int ans=,m=sum[l];
fo(j,,m)
{
if (!f[j])continue;
if (f[j]<=b)ans=max(ans,j);
while (pre&&(!g[r][pre]||g[r][pre]+f[j]>b))
{
pre--;
if (g[r][pre]&&g[r][pre]<=b)ans=max(ans,pre);
}
if (pre)ans=max(ans,pre+j);
}
answ[id]=ans;
}
fo(i,,q)printf("%d\n",answ[i]);
}