我只能说，好难，好巧，好复杂！！！
状态的表示，既有边的，又有点的，好几个数组记录中间答案。
我只能说，好nb。
充分利用了树形的特点，状态设置合理，无敌了呀。
虽然看懂了题解，看了一遍代码，自己写还是很困难。
#include <vector>
#include <cstdio>
#include <cstring>
#include <fstream>
#include <iostream>
#include <algorithm>
using namespace std;#define N 4011
#define E (3*N)
#define INF 0x7fffffffint next_node[N][N];
int best_drawoff_score[E][E];
int next_node_score[E][3];
int score[E];
int edge_id[N][N];
int dp[E][E];vector<int> adj[N];
int c[N];
int t, n, id;void init(){for (int i = 0; i<=3 * n; ++i){for (int j = 0; j<=3 * n; ++j){dp[i][j] = -INF;best_drawoff_score[i][j] = -INF;}}memset(next_node_score, -1, sizeof(next_node_score));
}int scoreMax(int ps, int s){if (s < 0) return 0;return score[edge_id[ps][s]];
}int precal(int start, int next, int current, int pre){next_node[start][current] = next;int res = 0;vector<pair<int, int> > candi;for (vector<int>::iterator it = adj[current].begin();it != adj[current].end(); ++it){if (*it == pre) continue;int tmp = precal(start, next, *it, current);res = max(res, tmp);candi.push_back(make_pair(-tmp, *it));}sort(candi.begin(), candi.end());for (int i = 0; i<3 && i<candi.size(); ++i){next_node_score[edge_id[pre][current]][i] = candi[i].second;}return score[edge_id[pre][current]] = res + c[current];
}int nextNode(int ps, int s, int v1, int v2 = -1){int e = edge_id[ps][s];int res = 0;if (v1 == next_node_score[e][res] || v2 == next_node_score[e][res]) ++res;if (v1 == next_node_score[e][res] || v2 == next_node_score[e][res]) ++res;return next_node_score[e][res];
}int calBestDrawoff(int ps, int s, int pt, int t){int e1 = edge_id[ps][s];int e2 = edge_id[pt][t];if (best_drawoff_score[e1][e2] != -INF){return best_drawoff_score[e1][e2];}if (t == s){int n1 = nextNode(ps, s, pt);int n2 = nextNode(pt, t, ps, n1);return best_drawoff_score[e1][e2] = scoreMax(t,n2);}int n1 = nextNode(pt, t, next_node[t][s]);best_drawoff_score[e1][e2] = scoreMax(t,n1)+c[t];best_drawoff_score[e1][e2] = max(best_drawoff_score[e1][e2], c[t] + calBestDrawoff(ps, s, t, next_node[t][s]));return best_drawoff_score[e1][e2];
}int gao(int ps, int s, int pt, int t){int e1 = edge_id[ps][s];int e2 = edge_id[pt][t];if (dp[e1][e2] != -INF) return dp[e1][e2];if (s == t){int n1 = nextNode(ps, s, pt);int n2 = nextNode(ps, s, pt, n1);return dp[e1][e2] = scoreMax(s,n1) - scoreMax(s,n2) + c[s];}int tmp = next_node[s][t];dp[e1][e2] = -gao(pt, t, s, tmp) + c[s];int n1 = nextNode(ps, s, tmp);dp[e1][e2] = max(dp[e1][e2], c[s] + scoreMax(s,n1) - calBestDrawoff(ps,s,pt,t));return dp[e1][e2];
}ofstream out("case.txt");int main(){freopen("D-large-practice.in","r",stdin);freopen("my_D.out","w",stdout);cin >> t;for (int cas = 1; cas <= t; ++cas){cin >> n;if(cas<=11&&cas>=7) out<<n<<endl;for (int i = 0; i<n; ++i){cin >> c[i];if(cas<=11&&cas>=7) out<<c[i]<<endl;adj[i].clear();}id = 0;for (int i = 0; i<n; ++i){edge_id[n][i] = id++;}for (int i = 0, j; i<n - 1; ++i){cin >> j;if(cas<=11&&cas>=7) out<<j<<endl;--j;adj[i].push_back(j);adj[j].push_back(i);edge_id[i][j] = id++;edge_id[j][i] = id++;}init();for (int i = 0; i<n; ++i){precal(n, i, i, n);for (vector<int>::iterator it = adj[i].begin();it != adj[i].end(); ++it){precal(i, *it, *it, i);}}int ans = -INF;for (int i = 0; i<n; ++i){int tmp = INF;for (int j = 0; j<n; ++j){int tmp2 = gao(n, i, n, j);tmp = min(tmp, tmp2);}ans = max(ans, tmp);}printf("Case #%d: %d\n", cas, ans);}
}