洛谷P3258 [JLOI2014] 松鼠的新家

yiweixxs / 2024-10-10 / 原文

Problem

给定一棵树，再给出其在树上的移动顺序,从$a_1$开始，在$a_n$结束，求出每个节点最少需要经过多少次(终点即$a_n$的最后一次到达不算)。其中$n\le3\times10^5$,$1\le a_i\le n$且保证a是1~n的排列

Solve

不难想到最少遍历的次数就是全走最短路，而一棵树中u->v的最短路必定是u->lca(u,v)->v
所以我们可以先跑一边tarjan求LCA，然后按照顺序遍历树即可。
但是测试点中大概率会通过类似链的树+叶子与根之间反复横跳的方法将程序的时间复杂度卡到$O(n^2)$，需要考虑优化
不难想到虽然是一棵树，但是每次从一个点到下一个点也是对一条树上的链进行区间增加，所以我们可以定义$f_i$是从i号点到根有一条增加x的链，这样我们可以直接在两个点与lca之间增加了，最后dfs求后序遍历出的和即可

Code

//注意事项:lca(u,v)可能就是u或v，此时特判，且除了起点都会多算一次，要减去
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<string>
#include<cstring>
#include<cstdlib>
#include<list>
#include<map>
#include<queue>
#include<stack>
#include<vector>
using namespace std;
int n,a[300005],f[300005],b[300005],lca[300005],q[300005],fa[300005],ans[300005];//lca[i]:i与前面点的lca
bool vis[300005];
vector<int> g[300005];
int find(int u){
    if(f[u]==u)return u;
    return f[u]=find(f[u]);
}
bool same(int u,int v){
    return find(u)==find(v);
}
bool unit(int u,int v){
    if(same(u,v))return false;
    f[v]=u;
    return true;
}
void dfs(int t){
    for(int i=0;i<g[t].size();i++){
        if(!vis[g[t][i]]){
            vis[g[t][i]]=1;
            fa[g[t][i]]=t;
            dfs(g[t][i]);
            unit(t,g[t][i]);
        }
    }
    if(vis[a[b[t]-1]]){
        lca[t]=find(a[b[t]-1]);
    }
    if(vis[a[b[t]+1]]){
        lca[a[b[t]+1]]=find(a[b[t]+1]);
    }
}
int dfs1(int t,int father){
    int sum=q[t];
    for(int i=0;i<g[t].size();i++){
        if(g[t][i]!=father){
            sum+=dfs1(g[t][i],t);
        }
    }
    ans[t]=sum;
    return sum;
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)f[i]=i;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        b[a[i]]=i;
    }
    for(int i=1,u,v;i<n;i++){
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    vis[1]=1;
    dfs(1);
    memset(vis,0,sizeof(vis));
    for(int i=2;i<=n;i++){
        if(lca[a[i]]!=a[i]&&lca[a[i]]!=a[i-1]){
            q[a[i]]++;
            q[fa[lca[a[i]]]]--;
            q[a[i-1]]++;
            q[lca[a[i]]]--;
            //cout<<a[i]<<" "<<a[i-1]<<" "<<lca[a[i]]<<" "<<fa[lca[a[i]]]<<endl;
        }else{
            int x=lca[a[i]]==a[i]?a[i-1]:a[i];
            q[x]++;
            q[fa[lca[a[i]]]]--;
            //cout<<x<<" "<<fa[lca[a[i]]]<<endl;
        }
    }
    dfs1(1,0);
    for(int i=1;i<=n;i++){
        if(b[i]>=2)ans[i]--;
        cout<<ans[i]<<"\n";
    }
    return 0;
}