2 条题解

  • 0
    @ 2026-5-8 19:49:52

    Solution

    本题即维护一棵树，可以加减关键点，改变边权，求一个点到最近的关键点的距离。

    有一个比较显然的点分树 + 线段树 + multiset 的做法，但是看起来常数巨大且无脑，复杂度是 O(nlog⁡2n)O(n \log^2 n) 但是……难写。

    如果强制限制关键点必须在查询点的子树中，比较简单，开一棵线段树维护所有关键点的深度，修改边权的时候区间加减，查询的时候询问区间最小值即可。

    对于子树外的点，考虑枚举它和询问点 uu 的 LCA，同时进行轻重链剖分，得到下图结构：

    发现我们需要维护一个点所有轻子树中关键点距离的最小值 viv_i。（修改一条边，只会对 O(log⁡n)O(\log n) 个 vv 产生修改。）

    用线段树维护 vi−depiv_i - dep_i，发现只有单点修改和区间加减，询问区间最小值，能做！

    复杂度 O(nlog⁡2n)O(n \log^2 n)。

    #include<bits/stdc++.h>
#define int long long
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXN=100000+10,INF=0x3f3f3f3f3f3f3f3f;
int n,q,sze[MAXN],son[MAXN],rev[MAXN],fa[MAXN],dep[MAXN],top[MAXN],dfn[MAXN],tot,fval[MAXN];
vector<pair<int,int>> G[MAXN];
void dfs1(int u,int f) {
	fa[u]=f,sze[u]=1;
	for(auto pr:G[u]) {
		int v=pr.first,w=pr.second;
		if(v==f) continue ;
		fval[v]=w,dep[v]=dep[u]+w,dfs1(v,u),sze[u]+=sze[v];
		if(sze[v]>sze[son[u]]) son[u]=v;
	}
	return ;
}
void dfs2(int u) {
	dfn[u]=++tot,rev[tot]=u;
	if(son[u]) top[son[u]]=top[u],dfs2(son[u]);
	for(auto pr:G[u]) {
		int v=pr.first,w=pr.second;
		if(v==fa[u]||v==son[u]) continue ;
		top[v]=v,dfs2(v);
	}
	return ;
}
int tr[MAXN];
void update(int pos,int v) {while(pos<=n) tr[pos]+=v,pos+=pos&-pos;return ;}
int query(int pos) {int ans=0;while(pos) ans+=tr[pos],pos-=pos&-pos;return ans;}
struct SEG {
	vector<int> mn,tag;
	void init(void) {
		return mn.resize(4*n+5),tag.resize(4*n+5),void();
	}
	#define lson (k<<1)
	#define rson (k<<1|1)
	#define mid (l+r>>1)
	void push_down(int k,int l,int r) {
		return tag[lson]+=tag[k],tag[rson]+=tag[k],mn[lson]+=tag[k],mn[rson]+=tag[k],tag[k]=0,void();	
	}
	void modify(int k,int l,int r,int pos,int v) {
		if(l==r) return mn[k]=v,void();
		push_down(k,l,r);
		if(pos<=mid) modify(lson,l,mid,pos,v);
		else modify(rson,mid+1,r,pos,v);
		return mn[k]=min(mn[lson],mn[rson]),void();
	}
	void update(int k,int l,int r,int x,int y,int v) {
		if(x<=l&&r<=y) return mn[k]+=v,tag[k]+=v,void();
		push_down(k,l,r);
		if(x<=mid) update(lson,l,mid,x,y,v);
		if(y>mid) update(rson,mid+1,r,x,y,v);	
		return mn[k]=min(mn[lson],mn[rson]),void();
	}
	int query(int k,int l,int r,int x,int y) {
		if(x>y) return INF;
		if(x<=l&&r<=y) return mn[k];
		push_down(k,l,r);
		if(y<=mid) return query(lson,l,mid,x,y);
		if(x>mid) return query(rson,mid+1,r,x,y);
		return min(query(lson,l,mid,x,y),query(rson,mid+1,r,x,y));	
	}
}s1,s2;
int cnt,flg[MAXN];
int cdep(int u) {return dep[u]+query(dfn[u]);}
int calc(int u,int fbd) {
	if(fbd==0) return s1.query(1,1,n,dfn[u],dfn[u]+sze[u]-1)-cdep(u);
	return min(s1.query(1,1,n,dfn[u],dfn[fbd]-1),s1.query(1,1,n,dfn[fbd]+sze[fbd],dfn[u]+sze[u]-1))-cdep(u);	
}
int Query(int u) {
	if(!cnt) return -1;
	int ou=u,ans=calc(u,0),val=cdep(u);
	while(u) {
		ans=min(ans,s2.query(1,1,n,dfn[top[u]],dfn[u])+val);
		u=top[u];
		if(u!=1) ans=min(ans,calc(fa[u],u)+val-cdep(fa[u])),u=fa[u];
		else break ;
	}
	return ans;
}
void renew(int u) {
	if(!u) return ;
	return s2.modify(1,1,n,dfn[u],calc(u,son[u])-cdep(u)),renew(fa[top[u]]),void();
}
signed main() {
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>q;
	ffor(i,1,n-1) {
		int u,v,w;
		cin>>u>>v>>w;
		G[u].push_back({v,w}),G[v].push_back({u,w});
	}
	dfs1(1,0),top[1]=1,dfs2(1);
	s1.init(),s2.init();
	ffor(i,1,n) s1.modify(1,1,n,i,INF),s2.modify(1,1,n,i,INF);
	ffor(i,1,q) {
		int op;
		cin>>op;
		if(op==2) {
			int u;
			cin>>u;
			if(flg[u]) cnt--,flg[u]=0,s1.modify(1,1,n,dfn[u],INF);
			else cnt++,flg[u]=1,s1.modify(1,1,n,dfn[u],cdep(u));
			renew(u);
		}
		else if(op==1) {
			int u;
			cin>>u,cout<<Query(u)<<'\n';
		}
		else {
			int a,b,w;
			cin>>a>>b>>w;
			if(fa[a]==b) swap(a,b);
			s2.update(1,1,n,dfn[b],dfn[b]+sze[b]-1,fval[b]-w);
			update(dfn[b],w-fval[b]),update(dfn[b]+sze[b],fval[b]-w);
			s1.update(1,1,n,dfn[b],dfn[b]+sze[b]-1,w-fval[b]),fval[b]=w;
			renew(a);
		}
	}
	return 0;
}
    • 0
      @ 2026-5-8 19:47:45

      TopTree 板子，每个族维护族内除界点外的点中到上下界点最近的距离和族路径长度，容易做到 O(nlog⁡n)O(n\log n)，轻松拿下最优解。

      #include<bits/stdc++.h>
#define N 100009
#define ll long long
#define INF 0x3f3f3f3f3f3f3f3fll
using namespace std;
struct node{
	int u,v,id;
	ll up,dn,len;
	char tp;
} tr[N<<1];
int n,q;
int pos[N],fa[N<<1],ls[N<<1],rs[N<<1];
int Rt;ll w[N];
bool is[N];
unordered_map<ll,int> mp;
int ppos[N];
int compress(node x,node y,node &ret){
	assert(x.v==y.u);
	int t=x.v;
	ret.up=min(x.up,y.up+x.len);if(is[t])ret.up=min(ret.up,x.len);
	ret.dn=min(y.dn,x.dn+y.len);if(is[t])ret.dn=min(ret.dn,y.len);
	ret.len=x.len+y.len;ret.u=x.u;ret.v=y.v;ret.tp='C';
	ret.tp='C';return t;
}
int rake(node x,node y,node &ret){
	ret.u=x.u;ret.v=y.v;assert(x.u==y.u);int t=x.v;
	ret.up=min(x.up,y.up);if(is[t])ret.up=min(ret.up,x.len);
	ret.dn=min(y.dn,x.up+y.len);if(is[t])ret.dn=min(ret.dn,x.len+y.len);
	ret.len=y.len;
	ret.tp='R';return t;
}
void upd(int u){
	if(!u)return;
	if(tr[u].tp=='C'){
		compress(tr[ls[u]],tr[rs[u]],tr[u]);upd(fa[u]);
	}
	else{
		rake(tr[ls[u]],tr[rs[u]],tr[u]);upd(fa[u]);
	}
}
ll qry(int x){
	if(is[x])return 0;
	if(!pos[x]){
		ll ret=INF;
		if(x==1){
			if(is[tr[Rt].v])ret=tr[Rt].len;
			return min(tr[Rt].up,ret);
		}
		else{
			if(is[tr[Rt].u])ret=tr[Rt].len;
			return min(tr[Rt].dn,ret);
		}
	}
	int y=pos[x];ll ret=INF,u,v;
	if(tr[y].tp=='C'){
		u=tr[ls[y]].len;v=tr[rs[y]].len;
		ret=min(tr[ls[y]].dn,tr[rs[y]].up);
	}
	else{
		u=tr[ls[y]].len;v=tr[ls[y]].len+tr[rs[y]].len;
		ret=min(tr[ls[y]].dn,tr[rs[y]].up+tr[ls[y]].len);
	}
	while(fa[y]){
		int z=fa[y];
		if(tr[z].tp=='C'){
			if(y==ls[z]){
				ret=min(ret,v+(is[tr[y].v]?0:tr[rs[z]].up));
				v+=tr[rs[z]].len;
			}
			else{
				ret=min(ret,u+(is[tr[y].u]?0:tr[ls[z]].dn));
				u+=tr[ls[z]].len;
			}
		}
		else{
			if(y==ls[z]){
				ret=min(ret,tr[rs[z]].up+u);
				if(is[tr[y].v])ret=min(ret,v);
				v=u+tr[rs[z]].len;
			}
			else{
				ret=min(ret,tr[ls[z]].up+u);
				if(is[tr[ls[z]].v])ret=min(ret,u+tr[ls[z]].len);
			}
		}
		y=z;
	}
	if(is[tr[y].u])ret=min(ret,u);
	if(is[tr[y].v])ret=min(ret,v);
	return ret;
}
basic_string<int> g[N],H[N];
int ffa[N],fps[N],son[N],sz[N],top[N],tot;
basic_string<int> st[N];
void dfs1(int u){
	sz[u]=1;
	for(int v:g[u]){
		if(v==ffa[u])continue;
		ffa[v]=u;fps[v]=++tot;
		tr[tot].u=u;tr[tot].v=v;tr[tot].id=tot;
		tr[tot].up=tr[tot].dn=INF;
		int t=mp[1ll*u*n+v];
		ppos[t]=tot;tr[tot].len=w[t];
		dfs1(v);
		if(sz[v]>sz[son[u]])son[u]=v;
		sz[u]+=sz[v];
	}
}
void dfs2(int u,int tp){
	st[tp]+=u;if(son[u])dfs2(son[u],tp);
	for(int v:g[u]){
		if(v==ffa[u]||v==son[u])continue;
		dfs2(v,v);
	}
}
basic_string<int> pre[N],vec[N];
int build(int u,int l,int r){
	if(l>r)return 0;
	if(l==r)return fps[vec[u][l]];
	int L=l,R=r;
	while(L+1<R){
		int mid=L+R>>1;
		if((pre[u][mid]-pre[u][l-1])*2<=pre[u][r]-pre[u][l-1])L=mid;
		else R=mid;
	}
	int mid=L;
	L=build(u,l,mid);R=build(u,mid+1,r);
	++tot;tr[tot].id=tot;
	int t=rake(tr[L],tr[R],tr[tot]);
	pos[t]=tot;fa[L]=fa[R]=tot;
	ls[tot]=L;rs[tot]=R;
	return tot;
}
int cbuild(int u,int l,int r){
	if(l>r)return 0;
	if(l==r)return fps[vec[u][l]];
	int L=l,R=r;
	while(L+1<R){
		int mid=L+R>>1;
		if((pre[u][mid]-pre[u][l-1])*2<=pre[u][r]-pre[u][l-1])L=mid;
		else R=mid;
	}
	int mid=L;
	L=cbuild(u,l,mid);R=cbuild(u,mid+1,r);
	++tot;tr[tot].id=tot;
	int t=compress(tr[L],tr[R],tr[tot]);
	pos[t]=tot;fa[L]=fa[R]=tot;
	ls[tot]=L;rs[tot]=R;
	return tot;
}
void dfs3(int u){
	for(int x:st[u]){
		if(!son[x])continue;
		pre[x]+=0;vec[x]+=0;
		for(int v:g[x]){
			if(v==son[x]||v==ffa[x])continue;
			dfs3(v);vec[x]+=v;
		}
		for(int i=1;i<vec[x].size();i++){
			pre[x]+=(pre[x][i-1]+sz[vec[x][i]]);
		}
		int rt=build(x,1,vec[x].size()-1);
		if(rt){
			++tot;tr[tot].id=tot;
			int t=rake(tr[rt],tr[fps[son[x]]],tr[tot]);
			pos[t]=tot;fa[rt]=fa[fps[son[x]]]=tot;
			ls[tot]=rt;rs[tot]=fps[son[x]];
			fps[son[x]]=tot;
		}
	}
	vec[u].clear();pre[u].clear();
	pre[u]+=0;vec[u]+=0;
	for(int x:st[u])vec[u]+=x;
	for(int i=1;i<vec[u].size();i++)pre[u]+=pre[u][i-1]+sz[ffa[vec[u][i]]]-sz[vec[u][i]];
	if(u!=1)fps[u]=cbuild(u,1,vec[u].size()-1);
	else Rt=fps[u]=cbuild(u,2,vec[u].size()-1);
}

int main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin>>n>>q;
	for(int i=1,x,y;i<n;i++){
		cin>>x>>y>>w[i],g[x]+=y,g[y]+=x;mp[1ll*x*n+y]=mp[1ll*y*n+x]=i;
	}
	dfs1(1);dfs2(1,1);dfs3(1);
	for(int i=1,op,x,y,z;i<=q;i++){
		cin>>op;
		if(op==1){
			cin>>x;ll t=qry(x);
			cout<<((t>=1e17)?-1:t)<<"\n";
		}
		else if(op==3){
			cin>>x>>y>>z;int t=mp[1ll*n*x+y];
			w[t]=z;tr[ppos[t]].len=z;upd(fa[ppos[t]]);
		}
		else{
			cin>>x;
			is[x]^=1;upd(pos[x]);
		}
	}
	return 0;
}
      • 1

      「NOISG 2022 Final」Grapevine

      信息

      ID
      11000
      时间
      3000ms
      内存
      1024MiB
      难度
      10
      标签
      递交数
      2
      已通过
      1
      上传者
      1. Language
      2. 兼容模式
      3. 主题
      3. Worker 0, 24ms
      4. Powered by Hydro v5.0.1 Community