自动搬运

查看原文

来自洛谷，原作者为

	sto_clx_orz log is the best

搬运于2025-08-24 22:23:53，当前版本为作者最后更新于2025-08-18 18:44:05，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

卡了一下午终于过了！！！
注意到题解区基本全是二离，和小部分的序列分块，点边分治，于是来写一篇纯种树分块。
这题看起来就不好直接线性空间，于是直接使用经典 trick 离线下来逐块处理。
先使用 topcluster，我们把每个块对询问的某一路径的贡献分为四类：

1. 路径完整穿过了当前块。
2. 路径只经过了当前块的上界点而未经过其下界点。
3. 路径只经过了当前块的下界点而未经过其上界点。
4. 路径完整在块内。

注意：下列子树均不包括根。
我们记 $U$ 表示在当前块下界点子树内的询问点总数，$V$ 表示不在当前块上界点子树内的询问点总数。
则第一类贡献是主链长度乘上 $U\times V$。
则第二类贡献是块内所有询问点到上界点长度和乘上 $V$。
则第三类贡献是块内所有询问点到下界点长度和乘上 $U$。
则第四类就是块内询问点距离和。
考虑加速，我们可以先处理出每个点是否在上下界点的前缀和，第一类可以直接算，第二三类再处理距离的前缀和，第四类二维前缀和就可以了。
常数极大。
你可能需要献祭同学与提交 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";
}