60pts求调
查看原帖
60pts求调
1183074
xzy_AK_IOI楼主2025/7/3 16:53
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define F(i,k,n) for (int i=(k);i<=(n);i++)
#define R(i,k,n) for (int i=(k);i>=(n);i--)
const int N=8e5+10;
const int inf=1e14;
int ls(int x){return x<<1;}
int rs(int x){return x<<1|1;}
struct segtree{
	int l,r,num,tag;
}tr[N<<2];
struct edge{
	int to,w;
};
int n,m,op,a,b,c,st[N],tot;
int dep[N],fa[N],sz[N],son[N],top[N],dfn[N];
int L[N];
int x[N];
int uu[N],vv[N],pp[N];
vector<edge>T[N];
void dfs1(int u){
	sz[u]=1;
	dep[u]=dep[fa[u]]+1;
	for (auto v:T[u]){
		if (v.to==fa[u]) continue;
		fa[v.to]=u;
		L[v.to]=L[u]+v.w;
		st[v.to]=v.w;
		dfs1(v.to);
		sz[u]+=sz[v.to];
		if (sz[v.to]>sz[son[u]]) son[u]=v.to;
	}
}
void dfs2(int u,int h){
	top[u]=h;
	tot++;
	dfn[u]=tot;
	x[tot]=st[u];
	if (son[u]) dfs2(son[u],h);
	for (auto v:T[u]){
		if (v.to==fa[u] || v.to==son[u]) continue;
		dfs2(v.to,v.to);
	}
}
void addtag(int p,int d){
	tr[p].tag+=d;
	tr[p].num+=(tr[p].r-tr[p].l+1)*d;
}
void pushup(int p){
	tr[p].num=tr[ls(p)].num+tr[rs(p)].num;
}
void pushdown(int p){
	if (tr[p].tag){
		addtag(ls(p),tr[p].tag);
		addtag(rs(p),tr[p].tag);
		tr[p].tag=0;
	}
}
void build(int l,int r,int p){
	tr[p].l=l;tr[p].r=r;
	if (l==r){
		tr[p].num=0;
		return;
	}
	int mid=(l+r)>>1;
	build(l,mid,ls(p));
	build(mid+1,r,rs(p));
	pushup(p);
}
void update(int l,int r,int p,int d){
	if (l<=tr[p].l && tr[p].r<=r){
		addtag(p,d);
		return ;
	}
	pushdown(p);
	int mid=(tr[p].l+tr[p].r)>>1;
	if (l<=mid) update(l,r,ls(p),d);
	if (mid+1<=r) update(l,r,rs(p),d);
	pushup(p);
}
int query(int l,int r,int p){
	if (l<=tr[p].l && tr[p].r<=r) return tr[p].num;
	pushdown(p);
	int mid=(tr[p].l+tr[p].r)>>1,ans=0;
	if (l<=mid) ans+=query(l,r,ls(p));
	if (mid+1<=r) ans+=query(l,r,rs(p));
	pushup(p);
	return ans;
}
int LCA(int x,int y){
	while (top[x]!=top[y]){
		if (dep[top[x]]<dep[top[y]]) swap(x,y);
		x=fa[top[x]];
	}
	return dep[x]>dep[y]?y:x;
}
int pathlength(int x,int y){
	return L[x]+L[y]-2*L[LCA(x,y)];
}
int querypath(int x,int y){
	int ans=0;
	while (top[x]!=top[y]){
		if (dep[top[x]]<dep[top[y]]) swap(x,y);
		ans+=query(dfn[top[x]],dfn[x],1);
		x=fa[top[x]];
	}
	if (dep[x]<dep[y]) swap(x,y);
	ans+=query(dfn[y],dfn[x],1);
	
	return ans;
}
void updatepath(int x,int y,int d){
	while (top[x]!=top[y]){
		if (dep[top[x]]<dep[top[y]]) swap(x,y);
		update(dfn[top[x]],dfn[x],1,d);
		x=fa[top[x]];
	}
	if (dep[x]<dep[y]) swap(x,y);
	update(dfn[y],dfn[x],1,d);
	update(dfn[x],dfn[x],1,-d);
}
bool check(int now){
	int jh=0;
    int maxn=0;
	F(i,1,m){
		if (pp[i]>now){
			updatepath(uu[i],vv[i],1);
            maxn=max(maxn,pp[i]-now);
			jh++;
		}
	}
	bool p=0;
	F(i,1,n){
		if (query(i,i,1)>=jh && x[i]>=maxn)p=1;
	}
	F(i,1,m){
		if (pp[i]>now){
			updatepath(uu[i],vv[i],-1);
		}
	}
	return p;
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n>>m;
	F(i,1,n-1){
		cin>>a>>b>>c;
		T[a].push_back({b,c});
		T[b].push_back({a,c});
	}
	dfs1(1);dfs2(1,1);
	build(1,n,1);
	F(i,1,m){
		cin>>uu[i]>>vv[i];
		pp[i]=pathlength(uu[i],vv[i]);
	}
	int l=0,r=inf,mid;
	while (l+1!=r){
		mid=(l+r)>>1;
		if (check(mid)){
			r=mid;
		}
		else l=mid;
	}
	cout<<r;
	return 0;
}
2025/7/3 16:53
加载中...