自动搬运

查看原文

来自洛谷，原作者为

	george0929 ด้้้้้็้้้็็็็็้้้้้็็็็็้้้้้้็็็็็้้้้้็็็็็้้้้้้็็็็็้้้้้็็็็็้้้้้้็็็็็้้้้้็็็็็้　蒟蒻一枚

搬运于2025-08-24 23:13:41，当前版本为作者最后更新于2025-08-20 13:34:24，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

给定一棵 $n$ 个节点的树，第 $i$ 条边可表示为四元组 $\{u_i,v_i,l_i,r_i\}$，其含义为这条边连接节点 $u,v$，并且有两个额外属性 $l,r$。对于每个 $i$ 求 $|\{x|\exists\ e \in \text{path}(1,i) : l_e \leq x \leq r_e\}|$，其中 $\text{path}(u,v)$ 表示 $u$ 到 $v$ 路径上所有边构成的集合。

由于要求出每个点到根链的信息，考虑 dfs 遍历整棵树，并使用某种数据结构实时维护到根链信息，在加入一条边时，往数据结构中加入 $(l,r)$，回溯时撤销操作。

我们每次撤销的都是上一次加入操作，因此撤销复杂度永远不会超过加入复杂度，因此我们只需要考虑区间的加入，然后再回溯的时候暴力撤销。

我们需要维护一个数据结构，支持每次往集合中加入一个区间并求出当前集合中区间并集的大小。这可以转化为每次将一个区间全部改为 $1$ 然后全局求和，显然线段树支持这个功能。

至此，本题完结，时空复杂度 $O(n\log n)$。

#include<bits/stdc++.h>
using namespace std;
int n,m;
struct edge{
	int v,l,r;
};
vector<edge> V[100005];
int b[200015],tot;
int getid(int x){
	return lower_bound(b+1,b+1+tot,x)-b;
}
struct node{
	int l,r;
	int len,sum;
	int tag;
}t[800015];
void build(int p,int l,int r){
	t[p].len=b[r+1]-b[l];
	t[p].l=l,t[p].r=r;
	if(l==r) return;
	int mid=(l+r)/2;
	build(p*2,l,mid);
	build(p*2+1,mid+1,r);
}
struct stk{
	int p,id;
	node val;
};
stack<stk> S;
void pushup(int p,int id){
	S.push({p,id,t[p]});
	t[p].sum=t[p*2].sum+t[p*2+1].sum;
}
void fil(int p,int id){
	S.push({p,id,t[p]});
	t[p].sum=t[p].len;
	t[p].tag=1;
}
void pushdown(int p,int id){
	S.push({p,id,t[p]});
	if(t[p].tag){
		t[p].tag=0;
		fil(p*2,id);
		fil(p*2+1,id);
	}
}
void modify(int p,int l,int r,int id){
	if(t[p].sum==t[p].len) return;
	if(l<=t[p].l&&t[p].r<=r){
		fil(p,id);
		return;
	}
	pushdown(p,id);
	int mid=(t[p].l+t[p].r)/2;
	if(mid>=l) modify(p*2,l,r,id);
	if(mid<r) modify(p*2+1,l,r,id);
	pushup(p,id); 
}
int ans[100005];
void dfs(int u,int fa){
	ans[u]=t[1].sum;
	for(auto nx:V[u]){
		int v=nx.v,l=nx.l,r=nx.r;
		if(v==fa) continue;
		modify(1,getid(l),getid(r+1)-1,v);
		dfs(v,u);
		while(!S.empty()&&S.top().id==v){
			int p=S.top().p;
			t[p]=S.top().val; 
			S.pop();
		}
	}
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<n;i++){
		int u,v,l,r;
		cin>>u>>v>>l>>r;
		V[u].push_back({v,l,r});
		V[v].push_back({u,l,r});
		b[++tot]=l,b[++tot]=r+1; 
	}
	b[++tot]=1,b[++tot]=m+1;
	sort(b+1,b+1+tot);
	tot=unique(b+1,b+1+tot)-b-1;
	build(1,1,tot-1);
	dfs(1,0);
	for(int i=2;i<=n;i++) cout<<ans[i]<<"\n"; 
	return 0; 
}