湖北省住房和城乡建设厅网站首页,陕西省城乡建设学校网站,wordpress无法编辑,网站开发流程及详解…调半天别的东西写错了#xff0c;心力交瘁。 思路还是不会。。 具体就是二分#xff0c;没想到#xff0c;然后再贪心。 一直没整明白一个数它要往别的树走的条件是什么#xff0c;日后研究。
#include iostream
#include cstdio
#include cstring心力交瘁。 思路还是不会。。 具体就是二分没想到然后再贪心。 一直没整明白一个数它要往别的树走的条件是什么日后研究。
#include iostream
#include cstdio
#include cstring
#include algorithm
#include set
#include vector
#include queue#define mid (lr1)
using namespace std;
typedef long long LL;
typedef pairint,int PII;
typedef pairLL,int PLI;
const int N 5e410, mod1e97;LL fa[N][20], le[N][20], deep[N], D; // deep i 到 1 的距离
vectorPIIG[N];
vectorint li;
vectorLLC, B, A;
int P[N], k, n;
bool dis[N];void dfs(int u, int f) // st 表
{for(int i 1;i 20;i )fa[u][i] fa[fa[u][i-1]][i-1], le[u][i] le[u][i-1] le[fa[u][i-1]][i-1]; for(auto x : G[u]){int a x.first;if(a f)continue;fa[a][0] u; le[a][0] x.second;deep[a] deep[u] x.second; dfs(a, u);}
}int se(int u, LL len) // u 走 len 最多走到哪.
{for(int i 19;i 0;i --)if(le[u][i] len) len - le[u][i], u fa[u][i];return u;
}void dfs2(int u, int fa)
{if(dis[u] || (G[u].size() 1 u ! 1)) return ;dis[u] 1;for(auto x : G[u]){int a x.first;if(a fa)continue;dfs2(a, u);dis[u] dis[a]; }return ;
}bool check(LL len) // ch函数
{C.clear(); B.clear(); A.clear();
// coutlenendl; D len;for(int i 1;i n;i ) dis[i] 0;for(int i 1;i k;i ) {int x se(P[i], len);if(x 1) C.push_back(P[i]);else dis[x] 1;}dfs2(1, 0);sort(C.begin(), C.end(), [](int a, int b){return D - deep[a] D - deep[b];}) ;for(auto x : C){int a se(x, deep[x]-1);if(!dis[a]len-deep[x]deep[a])dis[a] 1;else A.push_back(len - deep[x]);}
// for(int i 1;i n;i )coutdis[i] ;coutendl;for(auto i:li) if(!dis[i]) B.push_back(deep[i]);// for(auto x:A)coutx ;coutendl;
// for(auto x:B)coutx ;coutendl;sort(B.begin(), B.end());sort(A.begin(), A.end());int now 0, siz A.size();for(auto x : B){while(now ! siz A[now] x) now ;if(now siz)return 0;now ;}return 1;
}int main()
{ scanf(%d, n);for(int i 2;i n;i ){int a, b, c;scanf(%d%d%d, a, b, c);if(a b)swap(a, b);G[a].push_back({b, c});G[b].push_back({a, c});if(a 1) li.push_back(b);}for(int i 0;i 20;i ) le[1][i] 0x3f3f3f3f3f3f3f3f;dfs(1, 0); // st 初始化 sort(li.begin(), li.end(), [](int a, int b){return deep[a] deep[b];});scanf(%d, k);for(int i 1;i k;i )scanf(%d, Pi);LL l 0, r 1e14; // 二分答案 while(l r){if(check(mid)) r mid;else l mid1;}if(k li.size()) l -1;printf(%lld\n, l);return 0;
}
