285. 没有上司的舞会 - AcWing题库
题意是给你每个人的开心值，和每个人的顶头上司，如果每个人与自己的顶头上司不会同时去的前提下，问你最大的开心值是多少
树形dp
注释写在代码下面啦~
#include<iostream>
#include<cstring>
using namespace std;
const int N=2e6+10;
int h[N],ne[N],e[N],idx;
bool st[N];
int ha[N];
int f[N][2];
int n,m;
void add(int a,int b)
{e[idx]=b;ne[idx]=h[a];h[a]=idx++;
}
void dfs(int u)
{f[u][1]=ha[u];for(int i=h[u];i!=-1;i=ne[i]){int j=e[i];dfs(j);f[u][1]+=f[j][0];//这里其实是加上所有的子树的和//因为dfs把之前遍历的子树已经加过并且存储下来了，下面的就这样遍历然后加最后的结果就是全部子树的和了f[u][0]+=max(f[j][0],f[j][1]);}
}
int main(){memset(h,-1,sizeof(h));cin>>n;for(int i=1;i<=n;i++) cin>>ha[i];for(int i=1;i<=n-1;i++){int a,b;cin>>a>>b;add(b,a);st[a]=true;}int root=1;while(st[root]) root++;dfs(root);cout<<max(f[root][0],f[root][1])<<"\n";return 0;
}
/*
令f[u][0/1]为不选或者选u的以u为根的子树的最大值
f[u][1]=sum(f[j][0]);//u选了，下一个节点不能选
f[u][0]=sum(max(f[j][0],f[j][1]))//u不选，下一个节点可以选也可以不选
然后递归处理
*/1072. 树的最长路径 - AcWing题库
树的直径：
题意是给你一个无向图（树？）然后让你求树的直径
分类：把每个点都分类，然后求以每个点为根的最大值和次大值，最后求总的最大值
#include<iostream>
#include<cstring>
using namespace std;
const int N=2e6+10;
int h[N],ne[N],e[N],w[N],idx;
int n,res;
void add(int a,int b,int c)
{e[idx]=b;w[idx]=c;ne[idx]=h[a];h[a]=idx++;
}
int dfs(int u,int fa)
{int dist=0;int d1=0,d2=0;for(int i=h[u];i!=-1;i=ne[i]){int j=e[i];if(j==fa) continue;int d=dfs(j,u)+w[i];dist=max(dist,d);if(d>=d1) d2=d1,d1=d;else if(d>d2) d2=d;}res=max(res,d1+d2);return dist;
}
int main(){cin>>n;memset(h,-1,sizeof(h));for(int i=1;i<=n-1;i++){int a,b,c;cin>>a>>b>>c;add(a,b,c);add(b,a,c);}dfs(1,-1);cout<<res<<"\n";return 0;
}Problem - G - Codeforces
题意是给你一颗树，每个结点是黑色或者白色，问你有多少个子树里面的黑白两子的个数相等
还是做题做少了，这题我一开始想的是dfs然后记忆化
还是要多想，不知道再想想能不能想出来
这是一个树形dp的题
（凡是关于子树啊什么的，然后上下有关联的一般可以想想树形dp）
这个能想到树形dp其实也不难写了
然后写法要多多注意一下
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#define IOS ios::sync_with_stdio(false), cin.tie(0);
#include<iostream>
#include<map>
#include<set>
#include<cstdio>
#include<cstring>
#include<vector>
#include<stack>
#include<algorithm>
#include<cmath>
#include<queue>
#include<deque>
using namespace std;
#define int long long
typedef long long ll;
typedef pair<int,int> PAII;
const int N=2e6+10,M=5005,INF=1e18,mod=1e9+7;
int h[N],ne[N],e[N],idx;
int f[N][3];
int res;
char ch[N];
void add(int a,int b)
{e[idx]=b;ne[idx]=h[a];h[a]=idx++;
}
void dfs(int u,int fa)
{if(ch[u]=='W') f[u][1]=1;else if(ch[u]=='B') f[u][0]=1;for(int i=h[u];i!=-1;i=ne[i]){int j=e[i];if(j==fa) continue;dfs(j,u);f[u][1]+=f[j][1];f[u][0]+=f[j][0];}if(f[u][0]==f[u][1]) res++;
}
signed main(){//IOS;int T;//T=1;cin>>T;while(T--){ int n;cin>>n;for(int i=1;i<=n;i++) h[i]=-1,f[i][0]=0,f[i][1]=0;for(int i=2;i<=n;i++){int x;cin>>x;add(x,i);}for(int i=1;i<=n;i++) cin>>ch[i];res=0;dfs(1,-1);cout<<res<<"\n";}return 0;
}
/*
树形dp*/
