傳送門
\(\color{green}{solution}\)
嗯...其實我也不太會,所以大膽猜個結論吧(后來證了一下,然后放棄了...).
我們發現如果要使一個聯通塊的黑點數量為\(k\)的方案最少需要\(l\)個點,最多需要\(r\)個點
那么必然能找到一個點數在 \([l,r]\) 的連通塊使得包含\(k\)個黑點.
如果我們知道了這個結論, 那么這題就很zz了
這里只講最多需要多少個點(反之亦然).
我們定義這么一個狀態\(f_{i,j}\) 表示以\(i\) 為根的子樹有\(j\) 個黑點的方案最多能有多少點 那么就是一個樹形背包的事情.
轉移就是 \(f_{i, j}\) = \(\max{(f_{i,k}+f_{v, j-k}, k \in 0, j)}\) 其中v是\(i\) 的子樹,然后注意下邊界
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define fgr(i,u) for(int i=head[u];i;i=to[i])
#define fd(i,a,b) for(int i=a;i>=b;--i)
const int maxn=5010;
template <typename T> inline bool check_Max(T &x,const T&y) {return x<y?x=y,false:true;}
template <typename T> inline bool check_Min(T &x,const T&y) {return x>y?x=y,false:true;}
inline int gi() {int x=0; char o; bool f=true; for(;!isdigit(o=getchar());)if(o=='-')f=false;for(;isdigit(o);o=getchar()) x=(x<<1)+(x<<3)+(o&15); return f?x:~x+1;
}
int v[maxn<<1],to[maxn<<1],head[maxn],p;
inline void link(int a,int b){v[++p]=b; to[p]=head[a]; head[a]=p;}
int sz[maxn],col[maxn],Tx[maxn],Tn[maxn],g[maxn][maxn],f[maxn][maxn];
int n,m;
inline void dfs(int u,int pre) {sz[u]=1; g[u][1]=f[u][1]=col[u];fgr(i,u) if(v[i]^pre) {dfs(v[i],u); fd(j,sz[u],1) fd(k,sz[v[i]],1)check_Max(f[u][j+k],f[u][j]+f[v[i]][k]), check_Min(g[u][j+k],g[u][j]+g[v[i]][k]);sz[u]+=sz[v[i]];}rep(i,1,n) check_Max(Tx[i],f[u][i]),check_Min(Tn[i],g[u][i]);
}
int T;
int main() {
#ifndef ONLINE_JUDGEfreopen("1.in","r",stdin);
#endifT=gi();while(T--) {n=gi(); m=gi(); memset(f,0xc0,sizeof(f)); memset(g,0x3f,sizeof(g)); memset(head,0,sizeof(head));memset(Tn,0x3f,sizeof(Tn)); memset(Tx,0xc0,sizeof(Tx)); p=0;//printf("%d\n",f[0][0]);//de bugrep(i,2,n) {int u=gi(),v=gi(); link(u,v); link(v,u);}rep(i,1,n) col[i]=gi();dfs(1,0);rep(i,1,m) {int x=gi(),y=gi(); Tx[x]>=y&&Tn[x]<=y?puts("YES"):puts("NO");}puts("");}return 0;
}
轉載于:https://www.cnblogs.com/miecoku/p/10196276.html
總結
以上是生活随笔為你收集整理的[BZOJ 5072][Lydsy1710月赛]小A的树的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
