1、簡述C++中命名空間的作用。 答：避免重覆定義全局變數的問題。 2、定義兩個命名空間A 和 B 分別在A中和B中定義變數value。在main函數中將兩個空間的value列印出來。 #include "iostream" using namespace std; namespace A { in ...
思路：
註意到點對數量有 \(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;
}
