自动搬运

查看原文

来自洛谷，原作者为

	shadowice1984 これが勘違いでも、これが勘違いでも

搬运于2025-08-24 22:00:04，当前版本为作者最后更新于2018-04-25 19:20:30，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

大概是树上差分的题？

先介绍下什么是树上差分……(说实在的应该叫树上前缀和比较好)

大概是我们要算路径上的一些数(通常是求和)，然后计算路径信息的时候我们处理一些信息，然后通过算$Dep_{u}+Dep_{v}-2Dep_{lca(u,v)}$来计算路径上的信息

题目看起来非常有树链剖分的感觉……但是问题是，这道题没有修改这就导致题目难度大幅度下降了，所以我们先把每个点深度的k次方打一个表，之后我们因为要做减法，所以我们令$val_{i,k}$表示i到1号点路径上点深度的k次方之和……

然后问题来了，我们维护的是点权和，所以呢我们发现直接减的话会导致lca这个点没算，所以略微改一下公式，使lca这个点也被算一次

然后我们询问$u,v,k$的时候输出$val_{u,k}+val_{v,k}-val_{lca(u,v)}-val_{fa_{lca(u,v)}}$即可

问题就是如何找lca了……(欢迎使用TarjanO(n)求lca)

欢迎使用st表O(1)查询

然而最粗暴，可靠性最强，常数小而不会被轻易卡的算法还是倍增，所以这道题上一个倍增板子即可通过此题了~(不会倍增法求lca的话出门左转你站膜板区，包教包会~)

上代码~

#include<cstdio>
#include<algorithm>
using namespace std;typedef long long ll;const ll mod=998244353;const int N=3*1e5+10;const int M=60;
int n;int m;int v[2*N];int x[2*N];int al[N];int ct;ll dep[N];int fa[N][22];int book[N];ll val[N][M];
inline void add(int u,int V){v[++ct]=V;x[ct]=al[u];al[u]=ct;}ll mi[M];
inline void dfs(int u)//处理val的信息以及倍增的信息 
{
    book[u]=true;for(int i=0;fa[u][i];i++){fa[u][i+1]=fa[fa[u][i]][i];}
    for(int i=al[u];i;i=x[i])
    {
        if(book[v[i]]){continue;}
        fa[v[i]][0]=u;dep[v[i]]=dep[u]+1;
        for(int j=1;j<=50;j++){mi[j]=mi[j-1]*dep[v[i]]%mod;}
        for(int j=1;j<=50;j++){val[v[i]][j]=(mi[j]+val[u][j])%mod;}
        dfs(v[i]);
    }
}
inline int lca(int u,int v)//倍增求lca 
{
    if(dep[u]<dep[v]){swap(u,v);}int d=dep[u]-dep[v];
    for(int i=0;d;d>>=1,i++){if(d&1){u=fa[u][i];}}if(u==v){return u;}
    for(int i=20;i>=0;i--){if(fa[u][i]!=fa[v][i]){u=fa[u][i];v=fa[v][i];}}
    return fa[u][0]; 
}
int main()
{
    scanf("%d",&n);mi[0]=1;
    for(int i=1,u,v;i<n;i++){scanf("%d%d",&u,&v);add(u,v);add(v,u);}dfs(1);//dfs处理 
    scanf("%d",&m);
    for(int i=1,u,v,k;i<=m;i++)
    {
        scanf("%d%d%d",&u,&v,&k);int l=lca(u,v);//然后我们就直接减了，注意lca只算但是要算一次 
        printf("%lld\n",(val[u][k]+val[v][k]+2*mod-val[fa[l][0]][k]-val[l][k])%mod);
    }return 0;//拜拜程序~ 
}