树形DP杂题

引

对老师布置的题目稍微记录一下吧
也算对树形 $DP$ 的巩固

T1 Ostap and Tree

题目传送门

由于有 $距离k$ 的限制，设计二维 $dp$

设计状态：

$$\begin{gathered} f_{i,j}:i的子树内，离i最近的染色点与i距离为j \\ 且若j<=k,那么i的子树满足题目限制的方案数 \end{gathered}$$

状态转移：

考虑父节点 $u$ 与 子节点 $v$ 的合并
若枚举 $i,j$ ,那么考虑 $f_{u,i}$ 与 $f_{v,j}$ 可以转移到哪里
我们有 ：
1.当 $i+j\le k\ast 2$ 时
\quad $f_{u,\min (i,j)}\leftarrow f_{u,i}\ast f_{v,j}$
2.当 $i+j>k\ast 2$ 时
\quad $f_{u,\max (i,j)}\leftarrow f_{u,i}\ast f_{v,j}$
只能说都是状态设计的功劳

#include <algorithm>
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
typedef long long ll;
const int N=2e2+7,K=55 , INF=1e9;
const ll mod=1e9+7;
int n,k;
ll f[N][K],ans;
vector<int> G[N];
void dfs(int u,int fa) {f[u][0]=f[u][k+1]=1;for(int v:G[u]) {if(v== fa) continue; dfs(v,u);vector<ll> tmp(k*2+5) ;for(int i=0;i<=k<<1;i++) for(int j=0;j<=k<<1;j++) {if(i+j<=(k<<1))tmp[min(i,j+1)]=(tmp[min(i,j+1)]+f[u][i]*f[v][j]%mod)%mod;else tmp[max(i,j+1)]=(tmp[max(i,j+1)]+f[u][i]*f[v][j]%mod) %mod;}for(int i=0;i<=k<<1;i++) f[u][i]=tmp[i];}
}
int main() {scanf("%d%d",&n,&k);for(int i=1,u,v;i<n;i++) {scanf("%d%d",&u,&v);G[u].push_back(v),G[v].push_back(u);}dfs(1,0);for(int i=0;i<=k;i++) ans=(ans+f[1][i])%mod;printf("%lld\n",ans);
}

T2 实验比较

题目传送门

显然 ，根据 $<$ 关系建边， $=$ 缩点
若没有 $=$ ,那么这将是一道十分友好的题，稍微运用一下组合数学即可，状态也会十分简单
多设一维限制 $=$ 等号即可，注意判环的无解情况

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
inline int read() {int res = 0; bool bo = 0; char c;while (((c = getchar()) < '0' || c > '9') && c != '-');if (c == '-') bo = 1; else res = c - 48;while ((c = getchar()) >= '0' && c <= '9')res = (res << 3) + (res << 1) + (c - 48);return bo ? ~res + 1 : res;
}
inline char get() {char c; while ((c = getchar()) != '<' && c != '='); return c;
}
const int N = 135, M = 265, ZZQ = 1e9 + 7;
int n, m, X[N], Y[N], fa[N], ecnt, nxt[M], adj[N], go[M], in[N], cnt[N],
f[N][N], sze[N], C[N][N], g[N];
bool eq[N], its[N];
void init() {int i, j; for (i = 0; i <= 120; i++) C[i][0] = 1;for (i = 1; i <= 120; i++) for (j = 1; j <= i; j++)C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % ZZQ;
}
void add_edge(int u, int v) {nxt[++ecnt] = adj[u]; adj[u] = ecnt; go[ecnt] = v;nxt[++ecnt] = adj[v]; adj[v] = ecnt; go[ecnt] = u;
}
int cx(int x) {if (fa[x] != x) fa[x] = cx(fa[x]);return fa[x];
}
bool zm(int x, int y) {int ix = cx(x), iy = cx(y);if (ix != iy) fa[iy] = ix;else return 1;return 0;
}
void dfs(int u, int fu) {int i, j, k; sze[u] = f[u][1] = 1;for (int e = adj[u], v; e; e = nxt[e]) {if ((v = go[e]) == fu) continue; dfs(v, u);for (i = 1; i <= n; i++) g[i] = 0;for (i = 1; i <= sze[u] + sze[v]; i++) for (j = 1; j <= sze[u]; j++)for (k = 1; k <= sze[v]; k++) {int x = k - i + j; if (x < 0) continue;(g[i] += 1ll * f[u][j] * f[v][k] % ZZQ *C[i - 1][j - 1] % ZZQ * C[j - 1][x] % ZZQ) %= ZZQ;}for (i = 1; i <= sze[u] + sze[v]; i++) f[u][i] = g[i];sze[u] += sze[v]; }
}
int main() {int i; n = read(); m = read(); init();for (i = 1; i <= n; i++) fa[i] = i;for (i = 1; i <= m; i++) X[i] = read(),eq[i] = get() == '=', Y[i] = read();for (i = 1; i <= m; i++) if (eq[i]) zm(X[i], Y[i]);for (i = 1; i <= n; i++) its[in[i] = cx(i)] = 1;for (i = 1; i <= n; i++) fa[i] = i;for (i = 1; i <= m; i++)if (!eq[i]) {add_edge(in[X[i]], in[Y[i]]); cnt[in[Y[i]]]++;if (zm(in[X[i]], in[Y[i]])) return printf("0\n"), 0;}for (i = 1; i <= n; i++) if (its[i] && !cnt[i]) add_edge(n + 1, i);int ans = 0; dfs(n + 1, 0); for (i = 1; i <= sze[n + 1]; i++)ans = (ans + f[n + 1][i]) % ZZQ; cout << ans << endl;return 0;
}

T3 podjela

题目传送门

对题目中的限制，第二维开不下…
观察到答案的数量级应该是与 $n$ 同阶
严谨的证明一下就是 $ans\le n-1$
因为 $n-1$ 次后我们一定可以将每一条边遍历到，合理规划方案即可满足条件
那么就有了状态，将答案放进状态中，最后统计合法的最值即可

设计状态：

$$f_{i,j}:i的子树中，操作j次后，除i的节点都合法，i最多能获得的钱$$
注意，可能会欠款，也就是$f_{i,j}<0$

状态转移：

转移是个树上背包
$$\begin{gathered} f_{u,i+j+1}\leftarrow f_{u,i}+f_{v,j}(v的钱转移到i上) \\ 若v不欠款，即f_{v,j}\ge 0,就有f_{u,i+j}\leftarrow f_{u,i} \end{gathered}$$

$ans$就是第一个$f_{1,i}\ge 0$时取i即可

#include <algorithm>
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
typedef long long ll;
const int N=2e3+7,INF=1e9;
int n,X;
int v[N],f[N][N],sz[N],g[N];
vector<int>G[N];
void dfs(int u,int fa) {for(int i=0;i<=n;i++) f[u][i]=-INF;f[u][0]=X-v[u],sz[u]=1;for(int v:G[u]) {if(v==fa) continue;dfs(v,u); sz[u]+=sz[v];for(int i=0;i<=sz[u]+1;i++) g[i]=-INF;for(int i=0;i<=sz[u]-sz[v];i++) {for(int j=0;j<=sz[v];j++) {g[i+j+1]=max(g[i+j+1],f[u][i]+f[v][j]);if(f[v][j]>=0) g[i+j]=max(g[i+j],f[u][i]);}}for(int i=0;i<=sz[u]+1;i++) f[u][i]=g[i];}
}
int main(){scanf("%d%d",&n,&X);for(int i=1;i<=n;i++) scanf("%d",&v[i]);for(int i=1,u,v;i<n;i++) {scanf("%d%d",&u,&v);G[u].push_back(v),G[v].push_back(u);}dfs(1,0);for(int i=0;i<n;i++) if(f[1][i]>=0) return printf("%d\n",i),0;
}

T4 赛道修建

题目传送门

• $二分答案+贪心$ 即可，贪心时用好 $set$ 即可
  据说可以用 $vector$ 维护，不过又不卡 $set$ 不用白不用
  代码虚长

#include <algorithm>
#include <iostream>
#include <set>
using namespace std;
const int N=5e4+7;
int n,m,head[N],tot,ans,up;
struct node{ int to,next,w; }e[N<<1];multiset<int> s[N];
multiset<int>::iterator it;inline int read(){register int x=0,f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}return (f==1)?x:-x;
}void Add(int x,int y,int w){e[++tot]=(node) {y,head[x],w};head[x]=tot;
}int Dfs(int x,int fa,int k){s[x].clear();for(int i=head[x],y,val;i;i=e[i].next){y=e[i].to; if(y==fa) continue;val=Dfs(y,x,k)+e[i].w;if(val>=k) ans++;else s[x].insert(val);}int Max=0;while(!s[x].empty()){if(s[x].size()==1) return max(Max,*s[x].begin());it=s[x].lower_bound(k-*s[x].begin());if(it==s[x].begin()&&s[x].count(*it)==1) it++;if(it==s[x].end()){Max=max(Max,*s[x].begin());s[x].erase(s[x].begin());}else {ans++;s[x].erase(s[x].find(*it));s[x].erase(s[x].find(*s[x].begin()));}}return Max;
}int Check(int k){ans=0;Dfs(1,0,k);return (ans>=m);
}int Dfs1(int x,int fa){int sum1=0,sum2=0;for(int i=head[x],y;i;i=e[i].next){y=e[i].to; if(y==fa) continue;sum2=max(sum2,Dfs1(y,x)+e[i].w);if(sum1<sum2) swap(sum1,sum2);//最大与次大}up=max(up,sum1+sum2);return sum1;
}int main(){n=read(),m=read();for(int i=1,x,y,w;i<n;i++){x=read(),y=read(),w=read();Add(x,y,w);Add(y,x,w);}Dfs1(1,0);int l=1,r=up,mid;while(l<r){mid=(l+r+1)>>1;if(Check(mid)) l=mid;else r=mid-1;}printf("%d\n",l);
}

T5 Aerial Tramway

题目传送门

很有意思的一题，直入主题
引用别人的话：

我们首先发觉每个可以连的区间都是不相交的，只有相邻和包含关系，所以是 $O(n)$ 个（其实最多只有 $\frac{n}{2}$ 个）。然后这段区间跟相邻的是没有关系的。跟这段区间有关的只有包含的区间。所以我们可以递归的考虑这个问题。

一段区间与其包含的区间之间建边

设计状态：

$$f_{i,j,k}:i的子树分配了j个缆车，子树内被覆盖最多的点被覆盖了k次$$

状态转移

是一个经典的树上背包，注意 $前缀\max$ 优化,单次求解为 $O(n^2)$
总的复杂度为 $O(T{n}^2)$

#include <algorithm>
#include <iostream>
using namespace std;
const int N=2e2+7,INF=1e9;
int n,m,k,ca,cb,ans;
int x[N],y[N],b[N],g[N],nxt[N],sz[N],f[N][N][10],t[N][10];
struct st {int l,r,w;} a[N];
inline void up(int&a,int b){if(a<b)a=b;}
void dfs(int x){for(int a=0;a<=m;a++) for(int b=0;b<=k;b++)     f[x][a][b]=-INF;f[x][0][0]=0;for(int i=g[x];i;i=nxt[i]){dfs(i);for(int a=min(sz[x]+sz[i],m);i>=m;i--) for(int b=0;b<=k;b++) t[a][b]=f[x][a][b];for(int a=min(sz[x],m);~a;a--) for(int c=min(sz[i],m-a);~c;c--) {int t1=-INF,t2=-INF;for(int b=0;b<=k;b++) {up(t1,f[i][c][b]);       up(t2,f[x][a][b]);up(t[a+c][b],max(f[x][a][b]+t1,f[i][c][b]+t2));}}sz[x]+=sz[i];for(int a=min(sz[x],m);a>=m;a--) for(int b=0;b<=k;b++) f[x][a][b]=t[a][b];}if(!x)return;sz[x]++;for(int a=min(sz[x],m-1);~a;a--) for(int b=k-1;~b;b--) up(f[x][a+1][b+1],f[x][a][b]+::a[x].w);
}
int main(){int T;while(~scanf("%d%d%d",&n,&m,&k)){k--;for(int i=1;i<=n;i++) scanf("%d%d",&x[i],&y[i]);for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) if(y[i]==y[j]){bool flag=1;for(int k=i+1;k<j;k++) if(y[k]>=y[i]) {flag=0; break;}if(flag){if(i+1==j) b[++cb]=x[j]-x[i];else a[++ca]=(st){i+1,j-1,x[j]-x[i]};}}sort(b+1,b+cb+1,greater<int>());for(int i=2;i<=cb;i++) b[i]+=b[i-1];for(int i=1,j=0;i<=ca;i++){for(int k=1;k<=ca;k++)if(a[k].l<a[i].l&&a[k].r>a[i].r && (!j||a[k].w<a[j].w))j=k;nxt[i]=g[j],g[j]=i;}dfs(0);ans=-1;for(int i=m-cb;i<=m;i++) for(int j=0;j<=k;j++)up(ans,f[0][i][j]+b[m-i]);printf("Case %d: %d\n",++T,ans);for(int i=0;i<=ca;i++) g[i]=sz[i]=0;ca=cb=0;}
}

T6 Mousetrap

题目传送门

选好根，就是老鼠所在的位置 $t$ 。
观察好性质，老鼠一进入某个子树就一定会无路可走。
考虑完情况，老鼠往根的情况二分答案
详细的题解 贴个链接别人的Blog

再贴个自己的代码：

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
const int N=1e6+7,INF=1e9;
int n,t,m,l,r,ans;
int sum[N],f[N],fa[N];
vector<int> G[N];
void dfs(int u,int ff) {int MAX=0,_MAX=0,cnt=G[u].size()-1; fa[u]=ff;if(u!=t) sum[u]=sum[ff]+cnt-1+(u==m);for(int v:G[u]) if(v!=ff) {dfs(v,u); if(f[v]>=MAX) _MAX=MAX,MAX=f[v];else if(f[v]>_MAX) _MAX=f[v];}f[u]=_MAX+cnt;
}
bool check(int k) {int cnt=1;for(int u=m,tu=u;u!=t;u=fa[u],cnt++) {int x=0;for(int v:G[u]) if(v!=fa[u] && v!=tu && f[v]+sum[u]>k) {if(!cnt) return 0;x++,cnt--;}k-=x,tu=u;}return k>=0;
}
int main(){scanf("%d%d%d",&n,&t,&m); r=n<<1;for(int i=1,u,v;i<n;i++) {scanf("%d%d",&u,&v);G[u].push_back(v),G[v].push_back(u);}dfs(t,0);f[t]=0;// for(int i=1;i<=n;i++) printf("%d: %d\n",i,f[i]); puts("");// for(int i=1;i<=n;i++) printf("%d: %d\n",i,sum[i]);puts("");while (l<=r) {int mid=l+r>>1;if(check(mid)) ans=mid,r=mid-1;else l=mid+1;}printf("%d\n",ans);
}

结

其实还有三道题，但我太懒了，就不写了贴一题目链接
[PA2015] Rozstaw szyn
[POI2017] Sabotaż
[CEOI2017] Chase