题解：P6778 [Ynoi2009] rpdq
sto_clx_orz · · 题解
卡了一下午终于过了！！！
注意到题解区基本全是二离，和小部分的序列分块，点边分治，于是来写一篇纯种树分块。
这题看起来就不好直接线性空间，于是直接使用经典 trick 离线下来逐块处理。
先使用 topcluster，我们把每个块对询问的某一路径的贡献分为四类：
- 路径完整穿过了当前块。
- 路径只经过了当前块的上界点而未经过其下界点。
- 路径只经过了当前块的下界点而未经过其上界点。
- 路径完整在块内。
注意：下列子树均不包括根。
我们记
则第一类贡献是主链长度乘上
则第二类贡献是块内所有询问点到上界点长度和乘上
则第三类贡献是块内所有询问点到下界点长度和乘上
则第四类就是块内询问点距离和。
考虑加速，我们可以先处理出每个点是否在上下界点的前缀和，第一类可以直接算，第二三类再处理距离的前缀和，第四类二维前缀和就可以了。
常数极大。
你可能需要献祭同学与提交 inf 发来通过此题。
代码实现可能与上述题解略有区别。
#include<bits/stdc++.h>
using namespace std;
int n,m,B,fa[200005],key[200005],tot[200005],sum[200005],siz[200005],where[200005],upe[2511],doe[2511],cnt,exits[200005],lef[200005],rig[200005];
unsigned Ans[200005],dis[200005],disdoe[2511],disupe[2511],Dis[2001][2001];
vector<pair<int,unsigned>>Map[200005],nMap[200005];
vector<pair<int,int>>query;
vector<int>vec,block[2511];
inline void dfs1(int u,int f)
{
fa[u]=f;
for(auto&[v,w]:Map[u])
if(v!=f)
dfs1(v,u),
tot[u]+=tot[v],
sum[u]+=sum[v];
if(tot[u]>1||sum[u]>B||u==1)
key[u]=1;
if(key[u])
tot[u]=1,
sum[u]=0;
++sum[u];
}
inline void dfs2(int u,int f)
{
int now=vec.size(),flag=0;
for(auto&[v,w]:Map[u])
if(v!=f)
{
if((flag&&tot[v])||vec.size()-now>B)
{
++cnt;
upe[cnt]=u;
while(vec.size()>now)
block[cnt].push_back(vec.back()),
vec.pop_back();
}
flag|=tot[v];
dfs2(v,u);
}
if(key[u]&&vec.size())
{
++cnt;
upe[cnt]=u;
while(vec.size()>now)
block[cnt].push_back(vec.back()),
vec.pop_back();
}
vec.push_back(u);
}
inline void dfs3(int u,int f)
{
exits[u]=1;
for(auto [v,d]:Map[u])
if(v!=f)
dfs3(v,u);
}
inline void getdis(int u,int f)
{
for(auto&[v,d]:Map[u])
if(v!=f)
dis[v]=dis[u]+d,
getdis(v,u);
}
inline void getdis2(int u,int f)
{
for(auto&[v,d]:nMap[u])
if(v!=f)
dis[v]=dis[u]+d,
getdis2(v,u);
}
void solve(int x)
{
#pragma unroll
for(int i=1;i<=n;i++)
exits[i]=lef[i]=rig[i]=0,
nMap[i].clear();
for(auto [v,d]:Map[doe[x]])
if(v!=fa[doe[x]])
dfs3(v,doe[x]);
#pragma unroll
for(int i=1;i<=n;i++)
exits[i]+=exits[i-1];
sort(block[x].begin(),block[x].end());
for(int i=0;i<block[x].size();i++)
lef[block[x][i]]=rig[block[x][i]]=i+1;
#pragma unroll
for(int i=1;i<=n;i++)
if(!rig[i])
rig[i]=rig[i-1];
lef[n+1]=block[x].size()+1;
for(int i=n;i>=1;i--)
if(!lef[i])
lef[i]=lef[i+1];
for(int i:block[x])
for(auto[v,d]:Map[i])
if(where[v]==x||v==upe[x])
nMap[i].push_back({v,d});
for(auto[v,d]:Map[upe[x]])
if(where[v]==x||v==upe[x])
nMap[upe[x]].push_back({v,d});
dis[doe[x]]=0;
getdis2(doe[x],0);
unsigned len=dis[upe[x]];
for(int i=0;i<block[x].size();i++)
disdoe[i+1]=dis[block[x][i]];
for(int i=1;i<=block[x].size();i++)
disdoe[i]+=disdoe[i-1];
dis[upe[x]]=0;
getdis2(upe[x],0);
for(int i=0;i<block[x].size();i++)
disupe[i+1]=dis[block[x][i]];
for(int i=1;i<=block[x].size();i++)
disupe[i]+=disupe[i-1];
#pragma unroll
for(int i=1;i<=block[x].size();i++)
#pragma unroll
for(int j=1;j<=block[x].size();j++)
Dis[i][j]=0;
#pragma unroll
for(int i=0;i<block[x].size();i++)
{
int t=block[x][i];
dis[t]=0;
getdis2(t,0);
#pragma unroll
for(int j=0;j<i;j++)
Dis[i+1][j+1]=dis[block[x][j]];
}
#pragma unroll
for(int i=1;i<=block[x].size();i++)
#pragma unroll
for(int j=1;j<=block[x].size();j++)
Dis[i][j]+=Dis[i-1][j]+Dis[i][j-1]-Dis[i-1][j-1];
#pragma unroll
for(int i=1;i<=m;i++)
{
auto[l,r]=query[i-1];
unsigned L=lef[l],R=rig[r],Numd=exits[r]-exits[l-1],Numu=r-l+1-(R-L+1)-Numd;
Ans[i]+=(disdoe[R]-disdoe[L-1])*Numd+(disupe[R]-disupe[L-1])*Numu+len*Numd*Numu+Dis[R][R]-Dis[R][L-1]-Dis[L-1][R]+Dis[L-1][L-1];
}
}
int main()
{
ios::sync_with_stdio(false),cin.tie(0);
cin>>n>>m;
for(int i=1;i<n;i++)
{
int u,v,d;
cin>>u>>v>>d;
Map[u].push_back({v,d});
Map[v].push_back({u,d});
}
B=800;
dfs1(1,0);
dfs2(1,0);
block[++cnt]=vec;
upe[cnt]=1;
for(int i=1;i<=cnt;i++)
{
int flag=0;
for(int j:block[i])
if(key[j])
flag=1,
doe[i]=j;
if(!flag)
doe[i]=block[i].back();
}
for(int i=1;i<=m;i++)
{
int u,v;
cin>>u>>v;
query.push_back({u,v});
}
for(int i=1;i<=cnt;i++)
for(int x:block[i])
where[x]=i;
for(int i=1;i<=cnt;i++)
solve(i);
for(int i=1;i<=m;i++)
cout<<Ans[i]<<"\n";
}