[Ynoi2006] rldcot
题目描述
给定一棵 \(n\) 个节点的树，树根为 \(1\)，每个点有一个编号，每条边有一个边权。
定义 \(dep(x)\) 表示一个点到根简单路径上边权的和，\(lca(x,y)\) 表示 \(x,y\) 节点在树上的最近公共祖先。
共 \(m\) 组询问，每次询问给出 \(l,r\)，求对于所有点编号的二元组 \((i,j)\) 满足 \(l \le i,j \le r\) ，有多少种不同的 \(dep( lca(i,j))\)。
输入格式
第一行两个用空格隔开的数 \(n,m\)。
之后 \(n-1\) 行，每行三个用空格隔开的数 \(u,v,d\) 表示一条 \(u\) 到 \(v\) 边权为 \(d\) 的边。
之后 \(m\) 行，每行两个用空格隔开的数 \(l,r\) 表示一次询问。
输出格式
共 \(m\) 行，一行一个整数，表示询问的答案。
样例 #1
样例输入 #1
10 19
9 1 -4
9 8 2
8 10 5
9 7 -3
1 4 2
10 2 5
10 5 -1
7 3 -3
10 6 5
8 10
4 6
1 7
7 9
5 5
7 8
8 10
10 10
10 10
9 10
5 7
8 8
6 6
2 8
9 10
4 8
5 5
1 6
1 2
样例输出 #1
3
4
7
3
1
3
3
1
1
2
5
1
1
8
2
7
1
6
2
样例 #2
样例输入 #2
10 19
6 1 299830931
1 4 -565297395
1 7 -606073228
4 8 94253706
8 9 -576603423
4 3 116780102
3 5 620388954
7 10 -950023905
5 2 813045783
3 5
7 7
8 10
4 7
10 10
9 9
4 7
8 10
6 7
4 8
9 10
2 9
8 10
2 8
4 4
10 10
4 9
1 5
8 9
样例输出 #2
3
1
4
5
1
1
5
4
3
6
3
9
4
8
1
1
7
5
2
提示
对于 \(10\%\) 的数据，满足 \(1\le n,m \le 100\)。
对于另外 \(20\%\) 的数据，满足 \(1\le n,m \le 5000\)。
对于另外 \(20\%\) 的数据，满足 \(1\le n,m \le 50000\)。
对于另外 \(20\%\) 的数据，满足 \(d=1\)。
对于 \(100\%\) 的数据，满足 \(1\le n \le 10^5\)，\(1\le m \le 5 \times 10^5\)，所有数值为整数，\(-10^9 \le d \le 10^9\)。
要询问 \([l,r]\) 中有多少种不同的 \(dep_{lca(i,j)}\)
考虑枚举 \(lca(i,j)\)，此时如果 \((lca)(i,j)=x\)，那么 \(i,j\) 一定在两个不同的子树里。这个可以用一个启发式合并维护。
考虑固定 \(lca(i,j)=x\)，那么什么情况下 \((i,j)(i<j)\) 是有意义的
当且仅当不存在一个点对 \((i,k)\) 满足 \(k<j\) 且在两个不同的子树里。如果存在，包含了 \((i,k)\) 的询问一定包含了 \((i,j)\)。
可以用 set 维护，在 set 中二分出最大的小于它的数和最小的大于它的数。
此时我们有了很多可能对询问有贡献的点对，记作 \((l,r,dep)\) 吧。易证这些点对至多 \(O(nlog n)\) 个
那么可以用一个扫描线统计有多少个不同的 \(dep\)。具体而言，可以在需要时加入 \(l,r\)，对于每一种dep 维护最大的 \(l\)，然后再用树状数组维护就行了。可以在增加一个点对 \((l,r,dep)\) 时，更新 \(dep\) 最近出现的 \(l\)，并且树状数组中只有某种深度最近出现的 \(l\) 有贡献。这样，每个 dep 只会被算一次。
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5,M=5e5+5;
typedef long long LL;
struct edge{
int v,nxt,w;
}e[N<<1];
struct node{
int l,r;
LL dep;
bool operator<(const node&n)const{
return r<n.r;
}
}a[N<<5];
vector<int>g[N];
int hd[N],e_num,n,m,ans[N],to[N],lst[N],l[M],k,now,tr[N];
LL dep[N];
set<int>s[N];
map<LL,int>mx;
void add_edge(int u,int v,int w)
{
e[++e_num]=(edge){v,hd[u],w};
hd[u]=e_num;
}
void dfs(int x,int y)
{
to[x]=x;
for(int i=hd[x];i;i=e[i].nxt)
{
if(e[i].v==y)
continue;
dep[e[i].v]=dep[x]+e[i].w;
dfs(e[i].v,x);
if(s[to[e[i].v]].size()>s[to[x]].size())
to[x]=to[e[i].v];
}
for(int i=hd[x];i;i=e[i].nxt)
{
if(to[e[i].v]==to[x]||e[i].v==y)
continue;
for(set<int>::iterator j=s[to[e[i].v]].begin();j!=s[to[e[i].v]].end();++j)
{
set<int>::iterator it=s[to[x]].lower_bound(*j);
if(it!=s[to[x]].end())
a[++k]=(node){*j,*it,dep[x]};
if(it!=s[to[x]].begin())
{
a[++k]=(node){*(--it),*j,dep[x]};
// printf("%d %d %d %lld\n",*(--it),*j,x,dep[x]);
}
}
for(set<int>::iterator j=s[to[e[i].v]].begin();j!=s[to[e[i].v]].end();++j)
s[to[x]].insert(*j);
}
set<int>::iterator it=s[to[x]].lower_bound(x);
if(it!=s[to[x]].end())
a[++k]=(node){x,*it,dep[x]};
if(it!=s[to[x]].begin())
a[++k]=(node){*(--it),x,dep[x]};
s[to[x]].insert(x);
}
void update(int x,int y)
{
for(;x<=n;x+=x&-x)
tr[x]+=y;
}
int query(int x)
{
int ret=0;
for(;x;x-=x&-x)
ret+=tr[x];
return ret;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1,u,v,w;i<n;i++)
{
scanf("%d%d%d",&u,&v,&w);
add_edge(u,v,w);
add_edge(v,u,w);
}
dfs(1,0);
for(int i=1;i<=n;i++)
a[++k]=(node){i,i,dep[i]};
sort(a+1,a+k+1);
for(int i=1,r;i<=m;i++)
{
scanf("%d%d",l+i,&r);
g[r].push_back(i);
}
for(int i=1,cnt=0;i<=n;i++)
{
while(now^k&&a[now+1].r==i)
{
++now;
if(mx[a[now].dep])
update(mx[a[now].dep],-1),--cnt;
mx[a[now].dep]=max(mx[a[now].dep],a[now].l);
update(mx[a[now].dep],1),++cnt;
}
// printf("%d\n",cnt);
for(int j=0;j<g[i].size();j++)
ans[g[i][j]]=cnt-query(l[g[i][j]]-1);
}
for(int i=1;i<=m;i++)
printf("%d\n",ans[i]);
}