主播主播你这 1log 怎么跑不过 2log 啊
ETO_leader
·
·
题解
模拟赛题，场上没写明白。
考虑怎么 O(n) 的计算每一个询问。
考虑每个子树里面如果两个点没有相遇那么只计算 3 个界点一定是优的，我们考虑如果路径一定在 \mathrm{lca}(u,v) 的子树内话可以如下计算：
- 设 f_{u}(x,0/1/2), f_{v}(x,0/1/2) 分别表示 u 和 v 走到子树 x 的三个界点时的最短距离。
- 考虑转移，容易发现合并左右子树方便得多，所以我们把树三度化变成二叉树。
- 转移需要精细分讨，需要提前对于每个子树预处理三个界点之间的距离。
那么我们在 \mathrm{lca} 处合并左右子树的时候，计算 f(ls,0), f(rs,0) 的合并，以及 f(ls,2), f(rs,1) 的合并。
在子树外怎么办呢，容易发现不能走回头路，所以一定会经过一个比 \mathrm{lca} 更浅的点，或者走边 (v_k,v_1)，后者是好算的，前者怎么办。
我们直接从 \mathrm{lca} 往上 dp，换一种形式 g(u,0/1/2,0/1/2) 表示两个人分别在 u 子树的哪个界点。转移也是精细分讨。
以上做到 O(n\log n+nq)。
怎么做到更低呢，发现第一类转移和第二类转移都可以直接写成 (\min,+) 矩阵，此外发现第二类转移实际上只有 (0,1), (1,2), (0,2), (0,0) 四个状态是有用的，于是直接树链剖分可以做到 O(n\log n+q\log^2n)，但是这太蠢了。
主播主播还能更给力吗？
我们考虑怎么击杀掉那个询问的 $\log$。
我们继续树剖，每条重链建猫树做到 $O(1)$ 查询，预处理时间复杂度不变。
轻链怎么办，注意到我们一定是跳很多段前缀跳到某条链的链顶，所以我们对每个点预处理往上跳到每一条链链顶的的前缀积，预处理 $O(n \log n)$，单次询问 $O(1)$。
总复杂度 $O(n \log n+q)$。
:::info[code($O(n \log n+q\log n)$ 版本)]
```cpp
#include<bits/stdc++.h>
#define rep(i,a,b) for(auto i=a;i<b;++i)
using namespace std;
using lint=long long;
static constexpr auto _infl=(lint)(1e18l);
auto binarize(vector<tuple<int,int,lint>> es){
const auto n=(int)(es.size())+1;
vector<vector<pair<int,lint>>> gr(n);
for(auto&[u,v,w]:es) gr[u].emplace_back(v,w);
vector<tuple<int,int,lint>> res;
auto idx=n;
rep(i,0,n){
auto lnk=[&](auto __self,int u,vector<pair<int,lint>>l){
if(l.size()<3){
for(auto&[a,b]:l) res.emplace_back(u,a,b);
return;
}
++idx;
res.emplace_back(u,idx-1,0);
__self(__self,idx-1,vector<pair<int,lint>>(l.begin(),l.begin()+l.size()/2));
++idx;
res.emplace_back(u,idx-1,0);
__self(__self,idx-1,vector<pair<int,lint>>(l.begin()+l.size()/2,l.end()));
};
lnk(lnk,i,gr[i]);
}
return res;
}
template<const size_t d>
class matrix:public array<array<lint,d>,d>{
public:
friend auto operator*(matrix a,matrix b){
auto res=matrix();
rep(k,0,d) rep(i,0,d) if(a[i][k]<_infl) rep(j,0,d) res[i][j]=min(res[i][j],a[i][k]+b[k][j]);
return res;
}
matrix(){
rep(i,0,d) rep(j,0,d) (*this)[i][j]=_infl;
}
};
class tree{
private:
vector<vector<pair<int,lint>>> gr;
vector<int> uf,dep,uft;
vector<lint> vr,rw,ufw;
vector<array<array<lint,3>,3>> g;
lint global;
static constexpr auto lgw=21;
vector<vector<int>> up;
vector<vector<matrix<3>>> m3;
vector<matrix<4>> pm4;
auto dfs(int u,int ty,int f=-1){
uf[u]=f;dep[u]=(~f?dep[f]+1:0);
uft[u]=ty;
if(gr[u].empty()) return rw[u]=vr[u],void();
if(gr[u].size()==1){
const auto[s,sc]=gr[u][0];
ufw[s]=sc;
dfs(s,-1,u);
g[u]=g[s];
g[u][0][1]+=sc;
g[u][0][2]+=sc;
g[u][1][0]+=sc;
g[u][2][0]+=sc;
rw[u]=rw[s];
}else{
const auto[ls,lsc]=gr[u][0];
const auto[rs,rsc]=gr[u][1];
ufw[ls]=lsc;
ufw[rs]=rsc;
dfs(ls,0,u);
dfs(rs,1,u);
g[u][1][2]=min(g[ls][1][0]+lsc+rsc+g[rs][0][2],g[ls][1][2]+rw[ls]+g[rs][1][2]);
g[u][2][1]=min(g[ls][1][0]+lsc+rsc+g[rs][0][2],g[ls][1][2]+rw[ls]+g[rs][1][2]);
g[u][0][1]=min(g[ls][0][1]+lsc,g[ls][1][2]+rw[ls]+g[rs][0][1]+rsc);
g[u][1][0]=min(g[ls][0][1]+lsc,g[ls][1][2]+rw[ls]+g[rs][0][1]+rsc);
g[u][0][2]=min(g[rs][0][2]+rsc,g[rs][1][2]+rw[ls]+g[ls][0][2]+lsc);
g[u][2][0]=min(g[rs][0][2]+rsc,g[rs][1][2]+rw[ls]+g[ls][0][2]+lsc);
rw[u]=rw[rs];
}
}
auto initvals(){
rep(u,0,(int)(gr.size())){
up[0][u]=uf[u];
if(!~uf[u]){
rep(i,0,3) m3[0][u][i][i]=0;
rep(i,0,4) pm4[u][i][i]=0;
continue;
}
auto p=uf[u];
if(!~uft[u]){
m3[0][u][0][0]=ufw[u];
m3[0][u][1][1]=0;
m3[0][u][2][2]=0;
pm4[u][0][0]=ufw[u];
pm4[u][1][1]=ufw[u];
pm4[u][2][2]=0;
pm4[u][3][3]=0;
}else if(!uft[u]){
const auto[rs,rsw]=gr[p][1];
m3[0][u][0][0]=ufw[u];
m3[0][u][2][0]=rw[u]+g[rs][1][0]+rsw;
m3[0][u][2][2]=rw[u]+g[rs][1][2];
m3[0][u][0][2]=ufw[u]+rsw+g[rs][0][2];
m3[0][u][1][1]=0;
m3[0][u][0][1]=ufw[u]+rsw+g[rs][0][1]+rw[u]+g[u][2][1];
m3[0][u][2][1]=rw[u]+g[rs][1][0]+rsw+ufw[u]+g[u][0][1];
pm4[u][0][0]=ufw[u];
pm4[u][2][0]=g[rs][1][0]+rw[u]+rsw;
pm4[u][1][1]=ufw[u]+rw[u]+g[rs][1][2];
pm4[u][2][2]=rw[u]+g[rs][1][2];
pm4[u][0][2]=ufw[u]+rsw+g[rs][0][2];
pm4[u][3][3]=0;
pm4[u][1][3]=rw[u]+g[rs][1][0]+rsw+ufw[u];
}else{
const auto[ls,lsw]=gr[p][0];
m3[0][u][0][0]=ufw[u];
m3[0][u][1][0]=rw[ls]+g[ls][2][0]+lsw;
m3[0][u][1][1]=g[ls][2][1]+rw[ls];
m3[0][u][0][1]=g[ls][0][1]+ufw[u]+lsw;
m3[0][u][2][2]=0;
m3[0][u][0][2]=ufw[u]+lsw+g[ls][0][2]+rw[ls]+g[u][1][2];
m3[0][u][1][2]=rw[ls]+g[ls][2][0]+lsw+ufw[u]+g[u][0][2];
pm4[u][0][0]=ufw[u]+g[ls][2][1]+rw[ls];
pm4[u][1][1]=ufw[u];
pm4[u][2][1]=g[ls][2][0]+rw[ls]+lsw;
pm4[u][2][2]=rw[ls]+g[ls][1][2];
pm4[u][1][2]=ufw[u]+lsw+g[ls][0][1];
pm4[u][3][3]=0;
pm4[u][0][3]=rw[ls]+g[ls][2][0]+lsw+ufw[u];
}
}
rep(k,1,lgw) rep(u,0,(int)(gr.size())) if(~up[k-1][u]){
up[k][u]=up[k-1][up[k-1][u]];
m3[k][u]=m3[k-1][u]*m3[k-1][up[k-1][u]];
}else{
up[k][u]=-1;
m3[k][u]=m3[k-1][u];
}
auto initpm=[&](auto __self,int u)->void {
if(~uf[u]) pm4[u]=pm4[u]*pm4[uf[u]];
for(auto&[i,w]:gr[u]) __self(__self,i);
};
initpm(initpm,0);
}
auto kth_upper(int u,int k){
rep(i,0,lgw) if((k>>i)&1) u=up[i][u];
return u;
}
auto lca(int u,int v){
const auto ux=u,vx=v;
auto flp=false;
if(dep[u]<dep[v]) swap(u,v),flp=true;
auto cntu=0,cntv=0;
rep(i,0,lgw) if(((dep[u]-dep[v])>>i)&1){
cntu+=(1<<i);
u=up[i][u];
}
if(u==v){
if(flp) swap(cntu,cntv);
return make_tuple(u,kth_upper(ux,cntu),kth_upper(vx,cntv));
}
for(auto k=lgw-1;~k;--k) if(up[k][u]!=up[k][v]) u=up[k][u],v=up[k][v];
if(flp) swap(u,v);
return make_tuple(uf[u],u,v);
}
auto lcaval(int u, int l){
auto cur=g[u][0];
for(auto k=lgw-1;~k;--k) if(((dep[u]-dep[l])>>k)&1){
auto ncur=array<lint,3>{_infl,_infl,_infl};
rep(i,0,3) rep(j,0,3) ncur[j]=min(ncur[j],cur[i]+m3[k][u][i][j]);
cur=ncur;
u=up[k][u];
}
return cur;
}
auto binval(int u, array<array<lint,3>,3>z){
auto res=min({z[0][0],z[1][1],z[2][2]});
auto zw=array<lint,4>{z[0][1],z[0][2],z[1][2],res};
auto nzw=array<lint,4>{_infl,_infl,_infl,_infl};
rep(i,0,4) rep(j,0,4) nzw[j]=min(nzw[j],zw[i]+pm4[u][i][j]);
zw=nzw;
return min({zw[3],zw[2]+global});
}
public:
auto link(int u,int v,lint w){
gr[u].emplace_back(v,w);
}
auto setvr(int u,lint w){
vr[u]=w;
}
auto setglobal(lint w){
global=w;
}
auto init(){
dfs(0,-1);
initvals();
}
auto calc(int u,int v){
if(u>v) swap(u,v);
const auto[l,lpx,lpy]=lca(u,v);
const auto vl=lcaval(u,l);
const auto vr=lcaval(v,l);
auto cross=_infl;
if(u!=l&&v!=l){
const auto vls=lcaval(u,lpx);
const auto vrs=lcaval(v,lpy);
const auto lwx=(!uft[lpx])?vls:vrs;
const auto rwx=(uft[lpy]==1)?vrs:vls;
const auto ls=(!uft[lpx])?lpx:lpy;
cross=lwx[2]+rwx[1]+rw[ls];
}
array<array<lint,3>,3> apd;
for(auto&x:apd) fill(x.begin(),x.end(),_infl);
rep(i,0,3) rep(j,0,3) apd[i][j]=min({apd[i][j],vl[i]+vr[j],vl[j]+vr[i]});
return min(binval(l,apd), cross);
}
tree(int _n):gr(_n),g(_n),uf(_n),dep(_n),ufw(_n),uft(_n),vr(_n),rw(_n),up(lgw,vector<int>(_n)),m3(lgw,vector<matrix<3>>(_n)),pm4(_n),global(-1){}
};
int main(){
ios::sync_with_stdio(false),cin.tie(nullptr);
int n;cin>>n;
vector<int> chk(n);
vector<tuple<int,int,lint>> es;
rep(i,1,n){
int f;lint w;cin>>f>>w;--f;
es.emplace_back(f,i,w);
chk[f]=true;
}
vector<int> p;
rep(i,0,n) if(!chk[i]) p.emplace_back(i);
vector<lint> pw(p.size());
for(auto&x:pw) cin>>x;
es=binarize(es);
const auto xn=(int)(es.size())+1;
tree gr(xn);
for(auto&[u,v,w]:es) gr.link(u,v,w);
rep(i,0,(int)(p.size())-1) gr.setvr(p[i],pw[i]);
gr.setglobal(pw.back());
gr.init();
int q;cin>>q;
rep(i,0,q){
int u,v;cin>>u>>v;--u;--v;
cout<<gr.calc(u,v)<<'\n';
}
return 0;
}
```
:::