题目大意

给定一棵树,每个点有点权。每次询问从走到,步长为。如果某时距离不够,则一步走到,求途径点的点权和。

题解

分块,当时,我们暴力在树上行走;当时,我们预处理每个点隔一走到根的路径和直接询问即可。

比较复杂的地方在于讨论路径上的点的情况,大力讨论吧。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;

const int Maxn=50000;
const int MaxSqrtN=300;
const int MaxLogn=17;

int n,sn;
struct Edge{
    int v,nxt;
    Edge(){}
    Edge(int v0,int n0){
        v=v0;
        nxt=n0;
    }
}e[Maxn*2+5];
int head[Maxn+5],nume;

inline void addEdge(int u,int v){
    e[++nume]=Edge(v,head[u]);
    head[u]=nume;
    e[++nume]=Edge(u,head[v]);
    head[v]=nume;
}

int fa[Maxn+5][MaxLogn];
int dep[Maxn+5];
void dfs(int x,int from){
    for (int i=1;i<MaxLogn;i++) fa[x][i]=fa[fa[x][i-1]][i-1];
    for (int i=head[x];i;i=e[i].nxt){
        int v=e[i].v; if (v==from) continue;
        fa[v][0]=x; dep[v]=dep[x]+1;
        dfs(v,x);
    }
}

inline int swim(int x,int t){
    for (int i=0;t;i++,t/=2) 
        if (t&1) x=fa[x][i];
    return x;
}

int lca(int x,int y){
    if (dep[x]<dep[y]) swap(x,y);
    x=swim(x,dep[x]-dep[y]);
    if (x==y) return x;
    for(int i=MaxLogn-1;i>=0;i--){
        if (fa[x][i]==fa[y][i]) continue;
        x=fa[x][i]; y=fa[y][i];
    }
    return fa[x][0];
}

int val[Maxn+5],B[Maxn+5];
bool vis[Maxn+5];

int dis[Maxn+5][MaxSqrtN];
void dfsForDist(int x,int from,int K){
    dis[x][K]=val[x];
    if (dep[x]>K) dis[x][K]+=dis[swim(x,K)][K];
    for (int i=head[x];i;i=e[i].nxt){
        int v=e[i].v; if (v==from) continue;
        dfsForDist(v,x,K);
    }
}
inline int getDist(int u,int v,int K){
    int ret=0;
    for (;dep[u]>dep[v];u=swim(u,K)){
        ret+=val[u];
    }
    return ret;
}

void solve(int u,int v,int K,bool isBL){
    int f=lca(u,v);
    int len=dep[u]+dep[v]-2*dep[f];
    if (len<K){printf("%d\n",val[u]+val[v]); return;}
    int exa=len%K;
    int ans=(exa>0)?val[v]:0;

    v=swim(v,exa);
    int fu,fv; 
    fu=swim(f,(K-(dep[u]-dep[f])%K)%K);
    fv=swim(f,(K-(dep[v]-dep[f])%K)%K);
    if (!isBL){
        ans+=dis[u][K]-dis[fu][K];
        ans+=dis[v][K]-dis[fv][K];
    }else ans+=getDist(u,fu,K)+getDist(v,fv,K);
    if (f && (dep[f]-dep[u])%K==0) ans+=val[f];

    printf("%d\n",ans);
}


int main(){
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);

    //Input
    scanf("%d",&n);
    sn=sqrt(n);
    for (int i=1;i<=n;i++) scanf("%d",&val[i]);
    for (int i=1;i<n;i++){
        int x,y; scanf("%d%d",&x,&y);
        addEdge(x,y);
    }
    for (int i=1;i<=n;i++) scanf("%d",&B[i]);

    //Init LCA
    dep[0]=fa[0][0]=fa[1][0]=0; 
    dep[1]=1;
    dfs(1,0);

    //Solve
    for (int i=1;i<n;i++){
        int K; scanf("%d",&K);
        if (K<sn && !vis[K]) dfsForDist(1,0,K),vis[K]=true;
        solve(B[i],B[i+1],K,K>=sn);
    }

    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注