P9058 [Ynoi2004] rpmtdq 与 P9678 [ICPC2022 Jinan R] Tree Distance
思路:
注意到点对数量有 \(N^2\) 个,考虑丢掉一些无用的点对。
对于点对 \((x_1,y_1),(x_2,y_2)\),满足 \(x_1 \le x_2 < y_2 \le y_1\),即区间 \([x_2,y_2]\) 被 \([x_1,y_1]\) 包含,此时满足若询问到了 \([x_1,y_1]\),则一定会询问到 \([x_2,y_2]\)。
若满足 \(\operatorname{dis}(x_1,y_1) \ge \operatorname{dis}(x_2,y_2)\),那么此时可以将 \((x_1,y_1)\) 舍弃,因为若要用 \((x_1,y_1\)) 的贡献,不如直接去看 \((x_2,y_2)\) 的贡献,毕竟 \((x_1,y_1)\) 的贡献一定不会比 \((x_2,y_2)\) 更优。
那么我们可以定义若两个点对 \((x_1,y_1),(x_2,y_2)\) 满足以下条件,则称 \((x_1,y_1)\) 被 \((x_2,y_2)\) 支配:
-
\(x_1 \le x_2 < y_2 \le y_1\)。
-
\(\operatorname{dis}(x_1,y_1) \ge \operatorname{dis}(x_2,y_2)\)。
此时定义一个支配点对满足没有被任何一个点对支配,即我们需要找出所有的支配点对来计算贡献。
注意到是一个树上点对距离问题,考虑点分治解决。
令当前分治重心为 \(rt\),对于点 \(v\),令 \(S_v\) 表示当前联通块中所有满足 \(\operatorname{dis}(i,rt) \le \operatorname{dis}(v,rt)\) 的 \(i\) 组成的一个集合。
那么可以与 \(v\) 组成支配点对的点一定是 \(S_v\) 中 \(v\) 的前驱和后继,即 \(S_v\) 中 \(<v\) 中最大的数和 \(>v\) 中最小的数。
简单证一下,设 \(S_v\) 中 \(v\) 的前驱为 \(u\):
-
有 \(\operatorname{dis}(i,u) \le \operatorname{dis}(i,rt) + \operatorname{dis}(u,rt) \le \operatorname{dis}(i,rt) + \operatorname{dis}(v,rt) = \operatorname{dis}(i,v)\),即 \(\operatorname{dis}(i,u) \le \operatorname{dis}(i,v)\)。
-
注意到此时 \(i < u < v\) 或 \(u < v < i\),即 \((i,v)\) 被 \((i,u)\) 支配或 \((u,i)\) 被 \((v,i)\) 支配。
-
那么只有当 \(i=u\) 时,\((u,u)\) 点对不存在,\((u,v)\) 不会被其它 \(S_v\) 中的点对支配。
后继情况类似,就不多说了。
然后考虑如何快速找到支配点对,直接按照上面的方法找 \(S_v\),复杂度肯定是 \(O(N^2)\) 起步,考虑优化。
首先对于整个联通块的所有点,按照点的编号排序升序,然后维护一个 \(\operatorname{dis}(i,rt)\) 不降的单调栈。
那么有一个性质是,对于被点 \(i\) 弹出去的点 \(u\),肯定满足 \(i\) 是 \(u\) 后面第一个小于等于 \(\operatorname{dis}(u,rt)\) 的点且编号最小,即 \(i\) 是 \(S_u\) 中 \(u\) 的前驱;然后再倒着降序做一遍单调栈找后继即可。
此时我们来估算一下支配点对的数量,每个点最多被 \(\log N\) 个分治重心包含,每次包含最多增加 \(2\) 对支配点对,即总支配点对的数量为 \(N \log N\) 左右。
现在求出了全部的支配点对,即有贡献的点对,现在考虑如何求被一个区间包含的所有支配点对的最小贡献值,可以在线使用树套树,但是没必要。
考虑离线使用扫描线算法,因为树状数组不好维护后缀最值,考虑倒着扫左端点,然后对于每个点对,在左端点处将右端点贡献加入进去;那么对于一个在左端点的询问,就是一个前缀最小值。
时间复杂度为 \(O(N \log^2 N + Q \log N)\)。
完整代码:
#include<bits/stdc++.h>
#define Add(x,y) (x+y>=mod)?(x+y-mod):(x+y)
#define lowbit(x) x&(-x)
#define full(l,r,x) for(auto it=l;it!=r;it++) (*it)=x
#define Full(a) memset(a,0,sizeof(a))
#define open(s1,s2) freopen(s1,"r",stdin),freopen(s2,"w",stdout);
using namespace std;
typedef double db;
typedef unsigned long long ull;
typedef long long ll;
const ll N=2e5+10,M=1e6+10,INF=1e18;
bool Begin;
inline ll read(){
ll x=0,f=1;
char c=getchar();
while(c<'0'||c>'9'){
if(c=='-')
f=-1;
c=getchar();
}
while(c>='0'&&c<='9'){
x=(x<<1)+(x<<3)+(c^48);
c=getchar();
}
return x*f;
}
inline void write(ll x){
if(x<0){
putchar('-');
x=-x;
}
if(x>9)
write(x/10);
putchar(x%10+'0');
}
int n,q;
ll ans[M];
vector<int> G[N];
vector<pair<int,ll>> E[N],Q[N];
void add(int u,int v,int w){
E[u].push_back({v,w});
E[v].push_back({u,w});
}
namespace Lowbit{
ll a[N];
inline void init(){
for(int i=1;i<=n;i++)
a[i]=INF;
}
inline void add(int x,ll w){
for(int i=x;i<=n;i+=lowbit(i))
a[i]=min(a[i],w);
}
inline ll query(int x){
ll ans=INF;
for(int i=x;i;i-=lowbit(i))
ans=min(ans,a[i]);
return ans;
}
};
namespace LCA{
int p[N],t[N],z[N],d[N],fa[N];
ll dep[N];
inline void dfs1(int u,int f){
p[u]=1;
for(auto t:E[u]){
int v=t.first,w=t.second;
if(v==f)
continue;
dep[v]=dep[u]+w;
d[v]=d[u]+1;
fa[v]=u;
dfs1(v,u);
p[u]+=p[v];
if(p[v]>p[z[u]])
z[u]=v;
}
}
inline void dfs2(int u,int k){
t[u]=k;
if(!z[u])
return ;
dfs2(z[u],k);
for(auto t:E[u]){
int v=t.first;
if(v==fa[u]||v==z[u])
continue;
dfs2(v,v);
}
}
inline int Lca(int u,int v){
while(t[u]!=t[v]){
if(d[t[u]]<d[t[v]])
swap(u,v);
u=fa[t[u]];
}
return d[u]<d[v]?u:v;
}
inline ll dis(int u,int v){
return dep[u]+dep[v]-(dep[Lca(u,v)]<<1ll);
}
inline void init(){
dfs1(1,1);
dfs2(1,1);
}
};
namespace Tree{
int sum,cnt,top,Max,root;
int T[N],siz[N];
pair<int,ll> dis[N];
bool del[N];
inline void add(int x,int y){
if(x>y)
swap(x,y);
G[x].push_back(y);
}
inline void getroot(int u,int fa){
int s=0;
siz[u]=1;
for(auto t:E[u]){
ll v=t.first;
if(del[v]||v==fa)
continue;
getroot(v,u);
siz[u]+=siz[v];
s=max(s,siz[v]);
}
s=max(s,sum-siz[u]);
if(s<Max){
Max=s;
root=u;
}
}
inline void Get(int u,int p){
root=0;
sum=Max=p;
getroot(u,0);
getroot(root,0);
}
inline void getdis(int u,int fa,ll d){
dis[++cnt]={u,d};
for(auto t:E[u]){
int v=t.first,w=t.second;
if(v==fa||del[v])
continue;
getdis(v,u,d+w);
}
}
inline void calc(int u){
cnt=0;
getdis(u,0,0);
sort(dis+1,dis+cnt+1);
top=0;
for(int i=1;i<=cnt;i++){
while(top&&dis[i].second<=dis[T[top]].second){
add(dis[i].first,dis[T[top]].first);
top--;
}
T[++top]=i;
}
top=0;
for(int i=cnt;i>=1;i--){
while(top&&dis[i].second<=dis[T[top]].second){
add(dis[i].first,dis[T[top]].first);
top--;
}
T[++top]=i;
}
}
inline void solve(int u){
calc(u);
del[u]=1;
for(auto t:E[u]){
int v=t.first;
if(del[v])
continue;
Get(v,siz[v]);
solve(root);
}
}
void work(){
Lowbit::init();
LCA::init();
Get(1,n);
solve(root);
}
};
bool End;
int main(){
// open("A.in","A.out");
n=read();
for(int u,v,w,i=1;i<n;i++){
u=read(),v=read(),w=read();
add(u,v,w);
}
q=read();
for(int l,r,i=1;i<=q;i++){
l=read(),r=read();
Q[l].push_back({i,r});
}
Tree::work();
for(int i=n;i>=1;i--){
for(auto v:G[i])
Lowbit::add(v,LCA::dis(i,v));
for(auto t:Q[i])
ans[t.first]=Lowbit::query(t.second);
}
for(int i=1;i<=q;i++){
write(ans[i]==INF?-1:ans[i]);
putchar('\n');
}
cerr<<'\n'<<abs(&Begin-&End)/1048576<<"MB";
return 0;
}
热门相关:战斗就变强 我能看到隐藏机缘 风流医圣 闪婚总裁很惧内 大金主,你别假正经了