第三题这样暴力dfs能AC?我是先对权值排序再dfs，标记走过的节点做优化，只过了20% #include <cstdio> (802)#include <cstring> #include <algorithm> using namespace std; typedef pair<int, int> PII; const int N = 100010, M = N * 2; int h[N], e[M], ne[M], idx; int w[N]; PII node[N]; bool st[N];//标记走过的，以此处为头必不可能为最长路径 int n; int ans = 1; void add(int a, int b) { e[idx] = b, ne[idx] = h[a], h[a] = idx ++; } void dfs(int u, int s) { st[u] = true; ans = max(ans, s); for (int i = h[u]; ~i; i = ne[i]) { int j = e[i]; if (!st[j] && w[j] > w[u]) dfs(j, s + 1); } } int main() { memset(h, -1, sizeof h); scanf("%d", &n); // 记录点权 for (int i = 1; i <= n; i ++) { scanf("%d", &w[i]); node[i] = {w[i], i}; } // 建图 for (int i = 0; i < n - 1; i ++) { int u, v; scanf("%d%d", &u, &v); add(u, v), add(v, u); } // 给点权排序 sort(node, node + n); // 遍历树 for (int i = 1; i <= n; i ++) { if (!st[node[i].second]) dfs(node[i].second, 1); } printf("%d\n", ans); return 0; }