题目链接：here
题解：
假设现在有 n 条线段，假设 n 条边从小到达排序，如果这 n 条边中没有三条可以构成 三角形，那么这 n 条边必须满足关系：A[i]>=A[i-2]+A[i-1]，这里的 A[i]表示第 i 条边的大小。 假设 A[i]尽量取最小 A[i]=A[i-2]+A[i-1]，且 A[1]=A[2]=1，是不是就是一个斐波那契，也就 是对于一个 n 条边的集合，如果不存在三条边能构成一个三角形，那么最长的边至少为 f[n]， 表示斐波那契第 n 项。而题目中 A[i]<1e9，也就是只要 n>50，就必定存在三条边可以构成一 个三角形，所以我们只需要暴力加入两点路径上的边（如果大于 50，直接 Yes），然后对这 些边进行排序，枚举第 i 条边为最长边，贪心判断 A[i]是否小于 A[i-1]+A[i-2]即可
1 #include <cstdio> 2 #include <set> 3 #include <cstring> 4 #include <iostream> 5 #include <vector> 6 #include <algorithm> 7 using namespace std; 8 9 const int N = 1e5+10; 10 int n; 11 int tot, head[N], to[N<<1], nex[N<<1], len[N<<1]; 12 int f[N], dis[N], dep[N]; 13 14 void init() 15 { 16 tot = 0; 17 for(int i = 0; i <= n; ++ i) 18 { 19 head[i] = -1; 20 } 21 } 22 23 void addEdge(int x, int y, int l) 24 { 25 to[tot] = y; 26 len[tot] = l; 27 nex[tot] = head[x]; 28 head[x] = tot++; 29 } 30 31 void dfs(int u, int d) 32 { 33 dep[u] = d; 34 for(int i = head[u]; ~i; i = nex[i]) 35 { 36 int v = to[i]; 37 if(v == f[u]) continue; 38 dis[v] = len[i]; 39 f[v] = u; 40 dfs(v, d+1); 41 } 42 } 43 44 bool solve(int x, int y) 45 { 46 vector<int> vec; 47 while(vec.size() < 50 && x != y) 48 { 49 if(dep[x] < dep[y]) 50 { 51 vec.push_back(dis[y]); 52 y = f[y]; 53 } 54 else 55 { 56 vec.push_back(dis[x]); 57 x = f[x]; 58 } 59 } 60 if(vec.size()>=50) return true; 61 sort(vec.begin(), vec.end()); 62 for(int i = 0; i + 2 < vec.size(); ++ i) 63 { 64 if(vec[i] + vec[i+1] > vec[i+2]) return true; 65 } 66 return false; 67 } 68 69 int main() 70 { 71 int T; 72 scanf("%d", &T); 73 while(T--) 74 { 75 scanf("%d", &n); 76 init(); 77 for(int i = 1; i < n; ++ i) 78 { 79 int x, y, l; 80 scanf("%d%d%d", &x, &y, &l); 81 addEdge(x, y, l); 82 addEdge(y, x, l); 83 } 84 dfs(1, 0); 85 int m; 86 scanf("%d", &m); 87 for(int i = 0; i < m; ++ i) 88 { 89 int x, y; 90 scanf("%d%d", &x, &y); 91 puts(solve(x, y) ? "Yes" : "No"); 92 } 93 } 94 return 0; 95 }