NOIP模拟赛 T2树（分块）

题目描述

有一棵树，节点编号为$1$到$n$。还有$m$次查询，每次给出$l,r,x$，你需要回答从$x$号点走到编号在$l$到$r$之间的点的最小距离。

时限2s，空间256MB。

输入格式

第一行一个正整数$n$。

接下来$n-1$行，每行三个正整数$u,v,l$，表示$u$和$v$之间有一条长度为$l$的边。

接下来一行一个正整数$m$。

接下来$m$行，每行三个正整数$l,r,x$，表示一次询问。

输出格式

输出$m$行，每行一个整数，表示答案。

输入样例

3
1 2 1
1 3 1
3
2 3 1
2 3 2
3 3 2

输出样例

1
0
2

数据范围

n , m ≤ 1 0 5 n,m\\leq 10^5 n,m≤105，任意两点之间距离不超过 1 0 9 10^9 109

题解

首先，将$n$个数分成 n \\sqrt n n ​块。对于每次查询，先把非整块的部分存储在一个vector中，最后再用tarjan来$O(n)$处理。对于整块的部分，把询问的$x$放在对应各块的vector中。最后对每一块，都用这一块中的点在整棵树上做一个SPFA，然后对于其vector中的每个值，更新这个值的答案。

分块查询的时间复杂度为 O ( n n ) O(n\\sqrt n) O(nn ​)，tarjan的时间复杂度为$O(n)$。因为这是一棵树，所以SPFA可以看做是$O(n)$的，做 n \\sqrt n n ​次的总时间复杂度为 O ( n n ) O(n\\sqrt n) O(nn ​)。所以总时间复杂度为 O ( n n ) O(n\\sqrt n) O(nn ​)。

一些小优化

对于一组放入vector的将用来做tarjan的边，不能在两个点的vector中都放一次，否则可能会空间超限。要根据其dfs序来判断要将那个点放在另一个点的vector中。

code

#include<bits/stdc++.h>
using namespace std;
const int V=405,N=100000;
int n,m,bl,tot=0,cl=0,d[N*2+5],l[N*2+5],r[N*2+5],w[N*2+5];
int to[N+5],z[N+5],fa[N+5],ans[N+5],dis[N+5],dfn[N+5];
struct node{int x,id;
};
vector<node>s[N+5],vk[V+5];
queue<int>q;
void add(int xx,int yy,int zz){l[++tot]=r[xx];d[tot]=yy;r[xx]=tot;w[tot]=zz;
}
void dfs(int u,int f){dfn[u]=++cl;for(int i=r[u];i;i=l[i]){if(d[i]==f) continue;to[d[i]]=to[u]+w[i];dfs(d[i],u);}
}
int find(int ff){if(fa[ff]!=ff) fa[ff]=find(fa[ff]);return fa[ff];
}
void tarjan(int u){z[u]=1;for(int i=r[u];i;i=l[i]){if(!z[d[i]]){tarjan(d[i]);fa[d[i]]=u;}}for(auto it:s[u]){ans[it.id]=min(ans[it.id],to[u]+to[it.x]-2*to[find(it.x)]);}
}
void dd(int v){for(int i=1;i<=n;i++){dis[i]=2e9;z[i]=0;}for(int i=v*bl-bl+1;i<=v*bl;i++){dis[i]=0;z[i]=1;q.push(i);}while(!q.empty()){int u=q.front();q.pop();z[u]=0;for(int i=r[u];i;i=l[i]){if(dis[d[i]]>dis[u]+w[i]){dis[d[i]]=dis[u]+w[i];if(!z[d[i]]){z[d[i]]=1;q.push(d[i]);}}}}
}
void ask(int id,int l,int r,int x){int vx=(l-1)/bl+1,vy=(r-1)/bl+1;if(vx==vy){for(int i=l;i<=r;i++){if(dfn[x]<dfn[i]) s[i].push_back((node){x,id});else s[x].push_back((node){i,id});}}else{for(int i=l;i<=vx*bl;i++){if(dfn[x]<dfn[i]) s[i].push_back((node){x,id});else s[x].push_back((node){i,id});}for(int i=vy*bl-bl+1;i<=r;i++){if(dfn[x]<dfn[i]) s[i].push_back((node){x,id});else s[x].push_back((node){i,id});}for(int i=vx+1;i<=vy-1;i++){vk[i].push_back((node){x,id});}}
}
int main()
{scanf("%d",&n);bl=sqrt(n);for(int i=1,x,y,z;i<n;i++){scanf("%d%d%d",&x,&y,&z);add(x,y,z);add(y,x,z);}dfs(1,0);scanf("%d",&m);for(int i=1,l,r,x;i<=m;i++){scanf("%d%d%d",&l,&r,&x);if(l<=x&&x<=r) continue;ans[i]=2e9;ask(i,l,r,x);}for(int i=1;i<=n;i++) fa[i]=i;tarjan(1);for(int i=1;i<=(n-1)/bl;i++){if(!vk[i].size()) continue;dd(i);for(auto it:vk[i]){ans[it.id]=min(ans[it.id],dis[it.x]);}}for(int i=1;i<=m;i++){printf("%d\\n",ans[i]);}return 0;
}

天赋娱乐音乐