欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【NOIP2018模拟赛2018.8.28】plutotree

程序员文章站 2024-02-11 13:20:04
...

题目

【NOIP2018模拟赛2018.8.28】plutotree


题解

–部份分就是最短路嘛就不讲了
正解树上dp,233333
首先要知道我们dp的目的是什么:
对于一条u到v的路径,一共就只有四种情况
1. u和v直接跑lca
2. u跑到最近的叶子,跳到根,再跑到v
3. v跑到最近的叶子,跳到根,再跑到u
4. u和v都跑到最近的叶子,在根相遇
现在我们就发现了,要得到答案,首先要快速的求到每个节点到最近叶子的路径长度和最大权值
我们就可以dp
设down[i],是直接向下跑到叶子的情况
设dp[i],是可以跑回父亲节点再到叶子的情况
转移很简单,看代码就好了


代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
using namespace std;
const int MAXN=1e5+5;

int n,m;
vector<int>t[MAXN];
int fa[MAXN][20];
int w[MAXN];
int maxx[MAXN][20];
int deep[MAXN],d[MAXN];
struct hehe{
    int x;
    int y;
}dp[MAXN],down[MAXN];

void hb(hehe &a,hehe b){
    if(a.x>b.x)
        a=b;
    else if(a.x==b.x)
        a.y=max(a.y,b.y);
}


void build(){
    vector<int>q;
    q.push_back(1);
    deep[1]=1;
    d[1]=w[1];
    for(int h=0;h<q.size();h++){
        int x=q[h];
        for(int i=0;i<t[x].size();i++){
            int v=t[x][i];
            q.push_back(v);
            deep[v]=deep[x]+1;
            d[v]=d[x]+w[v];
        }
    }
    for(int j=1;j<=18;j++)
        for(int i=1;i<=n;i++){
            fa[i][j]=fa[fa[i][j-1]][j-1];
            maxx[i][j]=max(maxx[i][j-1],maxx[fa[i][j-1]][j-1]);
        }
    for(int i=q.size()-1;i>=0;i--){
        int x=q[i];
        hehe a;
        a.x=down[x].x+w[fa[x][0]];
        a.y=max(down[x].y,w[fa[x][0]]);
        hb(down[fa[x][0]],a);
    }
}

void solve(){
    vector<int>q;
    q.push_back(1);
    hb(dp[1],down[1]);
    for(int h=0;h<q.size();h++){
        int x=q[h];
        for(int i=0;i<t[x].size();i++){
            int v=t[x][i];
            q.push_back(v);
            dp[v]=down[v];
            hehe a;
            a.x=dp[x].x+w[v];
            a.y=max(dp[x].y,w[v]);
            hb(dp[v],a);
        }
    }
}

hehe lca(int x,int y){
    int u=x,v=y;
    int X,Y=max(maxx[x][0],maxx[y][0]);
    hehe ans;
    if(deep[x]<deep[y]){
        swap(x,y);
        swap(u,v);
    }
    for(int i=18;i>=0;i--)
        if(deep[fa[x][i]]>=deep[y]){
            Y=max(Y,maxx[x][i]);
            x=fa[x][i];
        }
    Y=max(Y,maxx[x][0]);
    if(x==y){
        X=d[u]-d[v]+w[v];
        ans.x=X;
        ans.y=Y;
        return ans;
    }
    for(int i=18;i>=0;i--)
        if(fa[x][i]!=fa[y][i]){
            Y=max(Y,maxx[x][i]);
            x=fa[x][i];
            Y=max(Y,maxx[y][i]);
            y=fa[y][i];
        }
    Y=max(Y,maxx[x][0]);
    Y=max(Y,maxx[y][0]);
    Y=max(Y,maxx[fa[x][0]][0]);
    X=d[u]+d[v]-d[fa[x][0]]*2+w[fa[x][0]];
    ans.x=X;
    ans.y=Y;
    return ans;
}

int main(){
//  freopen("plutotree.in","r",stdin);
//  freopen("plutotree.out","w",stdout);
    cin>>n>>m;
    for(int i=1;i<n;i++){
        int x;
        scanf("%d",&x);
        t[x].push_back(i+1);
        fa[i+1][0]=x;
    }
    for(int i=1;i<=n;i++){
        scanf("%d",&w[i]);
        maxx[i][0]=w[i];
    }
    for(int i=1;i<=n;i++){
        dp[i].x=down[i].x=1<<20;
        dp[i].y=down[i].y=0;
    }
    for(int i=1;i<=n;i++){
        if(!t[i].size()){
            down[i].x=down[i].y=w[i];
            hehe a;
            a.x=w[1]+w[i];
            a.y=max(w[1],w[i]);
            hb(dp[1],a);
        }
    }
    build();
    solve();
    while(m--){
        int u,v;
        scanf("%d%d",&u,&v);
        hehe ans=lca(u,v),now;
        now.x=dp[u].x+d[v];
        now.y=max(dp[u].y,maxx[v][18]);
        hb(ans,now);
        now.x=dp[v].x+d[u];
        now.y=max(dp[v].y,maxx[u][18]);
        hb(ans,now);
        now.x=dp[u].x+dp[v].x+w[1];
        now.y=max(max(dp[u].y,dp[v].y),w[1]);
        hb(ans,now);
        printf("%d %d\n",ans.x,ans.y);
    }
    return 0;
}
相关标签: 刷题之路