本来找的是树形结构，没想到几乎都是树形dp。。。
屑小明，给你一拳。（小明见问题被轻易攻破，相当不爽，于是又拿来问你。）
树形dp，找点权之和最大的一颗子树的点权和而且子树不能为空，以1为根节点，儿子的点权为负时剪枝就可以了。
#include <bits/stdc++.h>
using namespace std;
int i,j,n;
int a[16010],b[16010];
vector<int>v[16010];
void dfs(int x, int y) {
b[x]=a[x];
for(int i=0;i<v[x].size();i++) {
int t=v[x][i];
if (t!=y){
dfs(t,x);
if (b[t]>0) b[x]+=b[t];
}
}
}
int main() {
scanf("%d",&n);
for (int i=1;i<=n;i++) scanf("%d",&a[i]);
for (int i=1;i<n;i++) {
int x,y;
scanf("%d%d",&x,&y);
v[x].push_back(y);
v[y].push_back(x);
}
dfs(1,0);
int ans=b[1];
for(int i=1;i<=n;i++){
if(b[i]>ans) ans=b[i];
}
printf("%d",ans);
}
树形结构但不dp，是个二叉树，判断遍历中存在着多少个只有一棵子树的情况，不给中序遍历是因为中序遍历会确定左子树和右子树的情况，而仅靠前序和后序是没办法确定左右的，通过前序与后序的比对可以确定存在只有一子树的数量sum，因为不确定左右，所以sum*2就行了。
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int ans;
char str1[10010],str2[10010];
int main(){
scanf("%s",str1);
scanf("%s",str2);
for(int i=0;i<strlen(str1);i++)
for(int j=1;j<strlen(str2);j++)
if(str1[i]==str2[j]&&str1[i+1]==str2[j-1])
ans++;
printf("%d",1<<ans);
return 0;
}
树形dp，把每个节点都看成一个背包，容量是以这个节点为根的子树大小，组数就是连接的儿子个数，dp[u][j]=max(dp[u][j],dp[u][j-i]+dp[v][i]-edge[k].w)，最后输出dp[1][i]>=0时i的最大值。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m,k;
int head[3010],val[3010],dp[3010][3010];
struct node{
int to,next,w;
}edge[10000010];
void adde(int u,int v,int w)
{
edge[++k].to=v;
edge[k].next=head[u];
edge[k].w=w;
head[u]=k;
}
int dfs(int u)
{
if(u>n-m)
{
dp[u][1]=val[u];
return 1;
}
int sum=0,t;
for(int k=head[u];k;k=edge[k].next)
{
int v=edge[k].to;
t=dfs(v);
sum+=t;
for(int j=sum;j>0;j--)
{
for(int i=1;i<=t;i++)
{
if(j-i>=0) dp[u][j]=max(dp[u][j],dp[u][j-i]+dp[v][i]-edge[k].w);
}
}
}
return sum;
}
int main()
{
memset(dp,~0x3f,sizeof(dp));
scanf("%d%d",&n,&m);
for(int u=1;u<=n-m;u++)
{
int size,v,w;
scanf("%d",&size);
for(int j=1;j<=size;j++)
{
scanf("%d%d",&v,&w);
adde(u,v,w);
}
}
for(int i=n-m+1;i<=n;i++) scanf("%d",&val[i]);
for (int i=1;i<=n;i++) dp[i][0]=0;
dfs(1);
for (int i=m;i>=1;i--)
if (dp[1][i]>=0)
{
printf("%d",i);
break;
}
return 0;
}
树形dp，实际是找数的重心，就是每个节点到重心的距离和最小，这道题需要再乘以节点的权值，先以1为根，求出f[1]，即每个点到1的距离之和，在通过转移重心，输出最小的值即可。
重心转移：f[v]=f[u]+（sze[1]−sze[v]）−sze[v]，sze[u]表示以u为根的子树的大小，v为u的子节点。
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
long long int w[110],ans,f[110];
int n,i,j,num;
int head[10010],sze[10010];
struct node{
int to,next;
}e[101];
inline void add(int from, int to){
e[++num].to = to;
e[num].next = head[from];
head[from] = num;
}
void dfs(int u, int fa, int dep){
sze[u] = w[u];
for(int i = head[u]; i; i = e[i].next){
if(e[i].to != fa)
dfs(e[i].to, u, dep + 1), sze[u] += sze[e[i].to];
}
f[1] += w[u] * dep;
}
void dp(int u, int fa){
for(int i = head[u]; i; i = e[i].next)
if(e[i].to != fa)
f[e[i].to] = f[u] + sze[1] - sze[e[i].to] * 2, dp(e[i].to, u);
ans = min(ans, f[u]);
}
int main(){
ans=10000000;
scanf("%d",&n);
for(i=1;i<=n;i++){
int b,c;
scanf("%d%d%d",&w[i],&b,&c);
if(b){
add(i,b);add(b,i);
}
if(c){
add(i,c);add(c,i);
}
}
dfs(1,0,0);
dp(1,0);
printf("%lld",ans);
return 0;
}
5.会议 - 洛谷
树形dp，依旧是重心的转移，求f[1]，然后dfs，求 f[now]=f[fa]+n-2*size[now]，fa是now的父节点，n也就是size[1]啦。
#include <cstdio>
int d[50010],f[50010];
int n,cnt;
int size[50010];
bool vis[50010];
int head[50010];
struct Edge{
int to,nxt;
}edge[100010];
void add(int x,int y){
edge[++cnt].to=y;
edge[cnt].nxt=head[x];
head[x]=cnt;
}
void dfs1(int now){
size[now]=1;
for(int i=head[now];i;i=edge[i].nxt){
int to=edge[i].to;
if(d[to]) continue;
d[to]=d[now]+1;
dfs1(to);
size[now]+=size[to];
}
}
void dfs(int now,int fa){
f[now]=f[fa]+n-2*size[now];
for(int i=head[now];i;i=edge[i].nxt){
int to=edge[i].to;
if(to==fa) continue;
dfs(to,now);
}
}
int main(){
scanf("%d",&n);
for(int x,y,i=1;i<n;i++){
scanf("%d%d",&x,&y);
add(x,y);add(y,x);
}
d[1]=1;
dfs1(1);
int maxn=0,idx=1;
for(int i=1;i<=n;i++) maxn+=d[i];
maxn-=n;
f[1]=maxn;
for(int i=head[1];i;i=edge[i].nxt){
int to=edge[i].to;
dfs(to,1);
}
for(int i=2;i<=n;i++){
if(f[i]<maxn) maxn=f[i],idx=i;
}
printf("%d %d",idx,maxn);
return 0;
}
6.扩散 - 洛谷
寻找给出的坐标中两个距离最远且中间没有其他点的两个点，然后除以2，向上取整。
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int n,maxx,ans;
int x[55],y[55];
int g[55][55];
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
cin>>x[i]>>y[i];
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
g[i][j]=abs(x[i]-x[j])+abs(y[i]-y[j]);
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
g[i][j]=min(max(g[i][k],g[k][j]),g[i][j]);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
maxx=max(maxx,g[i][j]);
ans=(maxx+1)/2;
cout<<ans<<endl;
return 0;
}
树形dp，其实就是选与不选的问题，对于一个点，选了它那么它的子节点都不用选，不选它就要选它的所有子节点，说白了就是染色，设f[2000][2]，一种存选的情况，一种存不选，最后从两者中选小的输出。
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
struct node{
int to,nxt;
}e[20000];
int n,i,j,cnt;
int head[2000],f[2000][2];
void add(int a,int b){
e[++cnt].nxt=head[a];
e[cnt].to=b;
head[a]=cnt;
}
void dfs(int u,int fa){
f[u][1]++;
for(int i=head[u];i;i=e[i].nxt){
int t=e[i].to;
if(t==fa) continue;
dfs(t,u);
f[u][0]+=f[t][1];
f[u][1]+=min(f[t][0],f[t][1]);
}
}
int main(){
scanf("%d",&n);
for(i=1;i<=n;i++){
int a,b,k;
scanf("%d %d",&a,&k);
for(j=1;j<=k;j++){
scanf("%d",&b);
add(a+1,b+1);add(b+1,a+1);
}
}
dfs(1,0);
printf("%d",min(f[1][1],f[1][0]));
return 0;
}
不是树形dp，xor有一个性质:x ^ y ^ y = x，就是说将一个数xor两次同一个数后还是那个数，所以就直接dfs，在dfs中处理u，v到根节点的异或值，然后f[u]^f[v]。
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;
int n,m,k=0,head[100005],f[100005],vis[100005];
struct node{
int to,next,w;
}e[200005];
void add(int u,int v,int w)
{
e[++k].to=v;
e[k].next=head[u];
e[k].w=w;
head[u]=k;
}
void dfs(int u,int fa)
{
f[u]=fa;vis[u]=1;
for(int i=head[u];i;i=e[i].next)
if(!vis[e[i].to])
dfs(e[i].to,fa^e[i].w);
}
int main()
{
scanf("%d",&n);
int u,v,w;
for(int i=1;i<n;i++)
{
scanf("%d%d%d",&u,&v,&w);
add(u,v,w);add(v,u,w);
}
dfs(1,0);scanf("%d",&m);
for(int i=1;i<=m;i++)
{
scanf("%d%d",&u,&v);
printf("%d\n",f[u]^f[v]);
}
return 0;
}