10pts 求助(带详细注释)

4 
1 2 1 
1 3 2 
3 4 3 
2 
2 2

#include<bits/stdc++.h>
#define int long long
#define fr(i,r) for(int i=1;i<=r;++i)
#define For(i,l,r) for(int i=l;i<=r;++i)
#define Rof(i,r,l) for(int i=r;i>=l;--i)
#define eb emplace_back
#define pf pop_front
#define pb push_back
#define pii pair<int,int>
#define mp(x,y) make_pair(x,y)
#define msec 800
using namespace std;
const int N=5e4+10,M=1e5+10,logN=21,Inf=9223372036854775807;
char cch;
int res,zf;
inline int rd()
{
	while((cch=getchar())<45);
	if(cch^45)res=cch^48,zf=1;
	else res=0,zf=-1;
	while((cch=getchar())>=48)res=(res*10)+(cch^48);
	return res*zf;
}
inline void print(int x)
{
	if(x>9) print(x/10);
	putchar(x%10+'0');
}

int n=rd(),m;
int fa[N][logN]; //fa[u][k]:储存一个节点u向上跳2^k步指向的节点位置 
int dis[N][logN]; //dis[u][k]:储存一个节点u向上跳2^k步的总距离 
int top[N]; //top[u]:记录节点u所在链的链端 
int pos[N]; //pos[x]:记录第x支军队驻扎地点 

int fir[N],nex[M],to[M],len[M],rot;
inline void link(int s,int t,int l)
{
	nex[++rot]=fir[s];
	fir[s]=rot;
	to[rot]=t;
	len[rot]=l;
}

inline void dfs(int u,int Fa) //求解 top[] & fa[][] & dis[][] 数组 
{
	if(Fa==1) top[u]=u;
	else if(Fa) top[u]=top[Fa];
	fa[u][0]=Fa;
	fr(i,20) fa[u][i]=fa[fa[u][i-1]][i-1],dis[u][i]=dis[u][i-1]+dis[fa[u][i-1]][i-1];
	for(int e=fir[u];e;e=nex[e])
	{
		int v=to[e];
		if(v^Fa) dis[v][0]=len[e],dfs(v,u);
	}
}

int vis[N];//记录该节点与根节点之间有无军队驻守 
pii ava[N];//记录能够越过根节点的军队,第一维储存剩余可移动距离,第二维储存该军队是从根节点的哪个子节点过来的,以防出现跳到根节点后无法跳回的情况 
int cnt_av; //cnt_available:储存可以到达根节点的军队个数 
int need[N];//储存根节点的直接子节点中尚需要驻扎的点距根节点的距离 
int cnt_nd;//同理,易见 
inline void init()
{
	memset(vis,0,sizeof(vis));
	cnt_av=cnt_nd=0;
}

int flag;
inline void dfs2(int u,int Fa)//若子节点中的任何节点仍需驻军(一旦遇到已经驻军的节点就返回,故若走到叶子节点就说明这一条链上仍需驻军),flag就会变为0(如果走到叶子节点就说明该链的顶端节点仍需驻军,否则就标记vis[top]为1)
{
	if(vis[u]) return;//如果节点u已经驻军,就不用继续在其子树中查找了 
	bool flag_=0;
	for(int e=fir[u];e;e=nex[e])
	{
		int v=to[e];
		if(v^Fa) flag_=1,dfs2(v,u);
	}
	if(!flag_) flag=0;
}

inline bool check(int T)
{
	init();
	fr(i,m)//枚举每个军队 
	{
		if(dis[pos[i]][20]>=T)//dis[pos[i]][20]>=T:到节点1的距离  如果无法跳到根节点,尽量往上跳 
		{
			int T_=T,pos_=pos[i];
			Rof(j,20,0) if(dis[pos_][j]<=T_&&fa[pos_][j]>=2) T_-=dis[pos_][j],pos_=fa[pos_][j];
			vis[pos_]=1;
		}
		else ava[++cnt_av]=mp(T-dis[pos[i]][20],top[pos[i]]);//储存跳的到根节点的军队 
	}
	
	for(int e=fir[1];e;e=nex[e]) //检查1的子节点是否仍需要驻军 
	{
		int v=to[e];
		flag=1;
		dfs2(v,1);
		if(flag) vis[v]=1;
	}
	
	int newcnt=cnt_av;
	fr(i,cnt_av)//对于1的需要驻军的子节点v,如果存在一个点i从v跳上来并且剩余时间不足以使它跳回v,那让它停留在v节点最优,否则如果有另外的军队j跳到v,那么j在根节点的剩余时间一定大于点i在根节点的剩余时间(j的剩余时间可以走1->v,而i不能),那么j跳到其他点一定比i跳到其他点优,故直接让i原地驻扎
	{
		int u=ava[i].second;
		if(!vis[u]&&ava[i].first<dis[u][0]) vis[u]=1,ava[i].first=Inf,--newcnt;//将已经驻扎的军队距离设为Inf,这样的话在下一次排序时这些军队会被排到最后,从而排除在newcnt的范围外
	}
	sort(ava+1,ava+cnt_av+1);//将所有可到达根节点的军队按照剩余可行路程由小到大进行排序 
	
	for(int e=fir[1];e;e=nex[e])//统计仍需要驻军的子节点
	{
		int v=to[e];
		if(!vis[v]) need[++cnt_nd]=len[e];
	}
	sort(need+1,need+cnt_nd+1);//将需求从小到大排序
	
	Rof(i,newcnt,1) Rof(j,cnt_nd,1) if(need[j]>ava[i].first) return 0;
	return 1;
}

int k1,k2,k3;
int L,R,mid;
int ans=-1;//如果答案不存在,二分将直接返回-1 
signed main()
{
	fr(i,n-1) k1=rd(),k2=rd(),k3=rd(),link(k1,k2,k3),link(k2,k1,k3);
	dfs(1,0);
	m=rd();
	fr(i,m) pos[i]=rd();
	
	R=Inf;
	while(L<=R)
	{
		mid=L+R>>1;
		if(check(mid)) ans=mid,R=mid-1;
		else L=mid+1;
	}
	print(ans);
	
	return 0;
}