比较莫名奇妙的题目,明明是搜索题目居然放在了数学分类,完全找不到数学的影子。。
利用vector,遍历树,找出最大的子树路径,然后与次大的子树路径相加即为答案。
因为图表示这方面太渣,基本上抄袭了别人的代码= =
#include <bits/stdc++.h> using namespace std; // 大数,内存处理 #define INF 0x3f3f3f3f #define ll long long int #define MEM(a) memset(a, 0, sizeof(a)) #define MEMM(a) memset(a, -1, sizeof(a)) #define DEB(x, n) cout << (x) << " " << (n) << endl #define FOR(i, s, e) for(int (i) = (s); (i) < (e); (i)++) const double PI = acos(-1.0); #define CR printf("\n") // 调试用 template <class Type> void debug(Type a[], int len) { for(int i = ; i < len ; i++) { cout << a[i] << " "; } cout << endl; } const int maxn = 1e5 + 10; vector < pair <int, int> > node[maxn]; int ans; int ds(int to, int from) { int lmax = , lans = , lto; for(int i = ; i < node[to].size(); i++) { lto = node[to].at(i).first; if(lto != from) { lans = ds(lto, to) + node[to].at(i).second; ans = max(ans, lans + lmax); lmax = max(lmax, lans); } } return lmax; } int main() { #ifdef DEBUG // freopen("input", "r", stdin); //从input文件中读入 // freopen("output", "w", stdout); //输出到output文件 #endif char s[20]; bool c = true; int u, v, l; while(c) { for(int i = ; i < maxn; i++) node[i].clear(); while(1) { if(gets(s) == ) { c = false; break; } if(s[]) { sscanf(s, "%d%d%d", &u, &v, &l); node[u].push_back(make_pair(v, l)); node[v].push_back(make_pair(u, l)); } else break; } ans = ; ds(1, ); printf("%d\n", ans); } return ; }