本文共 5053 字，大约阅读时间需要 16 分钟。
[树形DP](https://cn.vjudge.net/contest/123963#overview)
#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define debug() puts("++++")#define gcd(a,b) __gcd(a,b)#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1#define fi first#define se second#define pb push_back#define sqr(x) ((x)*(x))#define ms(a,b) memset(a,b,sizeof(a))#define sz size()#define be begin()#define pu push_up#define pd push_down#define cl clear()#define lowbit(x) -x&x#define all 1,n,1#define rep(i,x,n) for(int i=(x); i<=(n); i++)using namespace std;typedef long long LL;typedef unsigned long long ULL;typedef pair P;const int INF = 0x3f3f3f3f;const LL LNF = 1e18;const int maxm = 1e6 + 10;const double PI = acos(-1.0);const double eps = 1e-8;const int dx[] = {-1,1,0,0,1,1,-1,-1};const int dy[] = { 0,0,1,-1,1,-1,1,-1};int dir[4][2] = { { 0,1},{ 0,-1},{-1,0},{ 1,0}};const int mon[] = { 0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};const int monn[] = { 0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};const int mod = 10056;#define inf 0x3f3f3f3f#define ll long longconst int maxn = 1e5+5;int t,n,m,x,y;int dp[maxn][2],v[maxn],a[maxn];int head[maxn];struct node{ int v,nxt;}e[maxn*2];int tot;void init(){ tot=0;//! ms(head,-1); ms(dp,0); ms(v,0);}void add(int u,int v){ e[tot].v=v; e[tot].nxt=head[u]; head[u]=tot++;}void dfs(int u,int fa){ //dp[u][0]=0; dp[u][1]=a[u]; for(int i=head[u]; i!=-1; i=e[i].nxt) { int v = e[i].v; if(v == fa) continue; dfs(v,u); dp[u][0] += max(dp[v][0],dp[v][1]); dp[u][1] += dp[v][0]; }}int main(){ while(~scanf("%d",&n)) { init(); for(int i=1;i<=n;i++) scanf("%d",&a[i]); for(int i=1;i<=n-1;i++) { scanf("%d%d",&x,&y); add(x,y); add(y,x); v[x]++; } scanf("\n0 0"); int root; for(int i=1;i<=n;i++) { if(!v[i]) { root=i; break; } } dfs(root,root); printf("%d\n",max(dp[root][0], dp[root][1])); }}/*【题意】【类型】树形DP【分析】【时间复杂度&&优化】【trick】【数据】*/
#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define debug() puts("++++")#define gcd(a,b) __gcd(a,b)#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1#define fi first#define se second#define pb push_back#define sqr(x) ((x)*(x))#define ms(a,b) memset(a,b,sizeof(a))#define sz size()#define be begin()#define pu push_up#define pd push_down#define cl clear()#define lowbit(x) -x&x#define all 1,n,1#define rep(i,x,n) for(int i=(x); i<=(n); i++)using namespace std;typedef long long LL;typedef unsigned long long ULL;typedef pair P;const int INF = 0x3f3f3f3f;const LL LNF = 1e18;const int maxm = 1e6 + 10;const double PI = acos(-1.0);const double eps = 1e-8;const int dx[] = {-1,1,0,0,1,1,-1,-1};const int dy[] = { 0,0,1,-1,1,-1,1,-1};int dir[4][2] = { { 0,1},{ 0,-1},{-1,0},{ 1,0}};const int mon[] = { 0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};const int monn[] = { 0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};const int mod = 10056;#define inf 0x3f3f3f3f#define ll long longconst int maxn = 1e4+5;int t,n,m,x,y,w,ans;int dp[maxn*2],v[maxn],a[maxn];int head[maxn];struct node{ int v,w,nxt;}e[maxn*2];int tot;void init(){ tot=0; //! ms(head,-1); ms(dp,0);}void add(int u,int v,int w){ e[tot].v=v; e[tot].w=w; e[tot].nxt=head[u]; head[u]=tot++;}int dfs(int u,int fa){ int Max=0; for(int i=head[u]; i!=-1; i=e[i].nxt) { int v = e[i].v; if(v == fa) continue; if(!dp[i]) dp[i]=dfs(v,u)+e[i].w; Max=max(Max,dp[i]); } return Max;}int main(){ while(~scanf("%d",&n)) { init(); for(int i=2;i<=n;i++) //! { scanf("%d%d",&y,&w); add(i,y, w),add(y,i, w); } for(int i=1;i<=n;i++) printf("%d\n",dfs(i,-1)); }}/*【题意】给出一颗树，求树中的每个顶点到其他所有顶点的最大值。【类型】树形DP，最短路【分析】题目给出10000个点，否则的话Floyd也是可以跑，但是给出的是一棵树，那么我们就可以用树形dp了1.（非两次DFS方法）每次从需要求的节点出发，然后遍历该树，期间更新该点的最长路。但是用DP数组存最长路的时候有一个问题，就是便利的方向，如果不考虑方向的话肯定是错的，那么可以转换一下，DP数组不存点的最长路，存边的最长路，这样使用邻接链表村边的化就可以考虑到方向了。具体看代码。2.（两次DFS方法）首先，我们分析发现，当前一个点的最大距离只有两种来源:一种是它到叶子节点的最大距离一种是经过根节点的最大距离（也就是根节点到叶子节点 不经过 当前点的最大距离 + 跟到当前点的距离）实现的话发现要求不经过当前点，所以我们求到叶子节点向上的最大距离时还要维护一个次短距离。首先一遍dfs，求出从任意一个节点到叶子节点的最短路dp[i][0]和次段路dp[i][1]，算是一个预处理。然后，定义状态dp[i][2]从 i 点出发经过 root 节点的最短路。状态转移方程：dp[child][2] = max(dp[father][2]，dp[child][0]+ child.cap == dp[father][0]？dp[father][1]：dp[father][0])+child.cap ;（PS：另一种方法可以在第一次dfs时把从叶子节点到根节点经过的点标记出来，然后在第二次更新的时候如果遇到是经过的点，然后直接选择次短路，可以尝试一下）【时间复杂度&&优化】【trick】dp数组必须开到1e5*2，否则TLE（不明觉厉？？？有两种做法。1、求树的直径。两遍dfs找到树的直径，根据树的直径的性质，从任意一个点出发走的最长距离，一定是到直径的端点。2、树形dp。也就是我写的做法。首先从根节点开始往下搜，每次跟新以这个节点为根节点的最远距离和次远距离。这样一次dfs之后，根节点的fir就是他所能达到的最远距离。然后从根开始往下搜，如果这个点的父亲节点的最远距离需要经过这个点，那么只需比较（父亲节点的次远距离+dis）和（自己这个点的最远距离），然后跟新这个点的次远和最远。如果不需要经过，那么比较 （父亲节点的最远距离+dis）和（自己这个点的最远距离），然后更新即可。【数据】*/
转载于:https://www.cnblogs.com/Roni-i/p/9428071.html
