求助树剖
  • 板块灌水区
  • 楼主Polariserist
  • 当前回复0
  • 已保存回复0
  • 发布时间2020/12/19 16:04
  • 上次更新2023/11/5 05:56:23
查看原帖
求助树剖
171513
Polariserist楼主2020/12/19 16:04

各位大佬,帮忙看看蒟蒻的树剖出了什么毛病。。? (请忽视main)

#include<bits/stdc++.h>
using namespace std;
const int maxn=100010;
int dep[maxn],hson[maxn],madfsn[maxn],sz[maxn],fa[maxn],dfsn[maxn],top[maxn],N,M,R,P,A[maxn],B[maxn];
vector<int>edges[maxn];
void build(int l=1,int r=n,int p=1){
    if(l==r){
        tval[p]=A[l];
        return;
    }
    if(!ls[p]){
        ls[p]=++cnt;
    }
    if(!rs[p]){
        rs[p]=++cnt;
    }
    int mid=(l+r)/2;
}
void dfs1(int p,int d=1)
{
    int size=1,ma=0;
    dep[p]=d;
    for(auto q:edges[p])
        if(!dep[q]){
            dfs1(q,d+1);
            fa[q]=p;
            size+=sz[q];
            if(sz[q]>ma)
                hson[p]=q, ma=sz[q];
        }
    sz[p]=size;
}
int cnt;
void dfs2(int p){
    madfsn[p]=dfsn[p]=++cnt;
    if(hson[p]!=0){
        top[hson[p]]=top[p];
        dfs2(hson[p]);
        madfsn[p]=max(madfsn[p],madfsn[hson[p]]);
    }
    for(auto q:edges[p])
        if(!top[q]){
            top[q]=q;
            dfs2(q);
            madfsn[p]=max(madfsn[p],madfsn[q]);
        }
}
int lca(int a,int b){
    while(top[a]!=top[b]){
        if (dep[top[a]]>dep[top[b]])
            a=fa[top[a]];
        else
            b=fa[top[b]];
    }
    return(dep[a]>dep[b]?b:a);
}
void update_path(int x,int y,int z){
    while(top[x]!=top[y]){
        if(dep[top[x]]>dep[top[y]]){
            update(dfsn[top[x]],dfsn[x],z);
            x=fa[top[x]];
        }
        else
        {
            update(dfsn[top[y]],dfsn[y],z);
            y=fa[top[y]];
        }
    }
    if (dep[x]>dep[y])
        update(dfsn[y],dfsn[x],z);
    else
        update(dfsn[x],dfsn[y],z);
}
int query_path(int x, int y){
    int ans=0;
    while(top[x]!=top[y])
    {
        if (dep[top[x]]>dep[top[y]])
        {
            ans+=query(dfsn[top[x]],dfsn[x]);
            x=fa[top[x]];
        }
        else
        {
            ans+=query(dfsn[top[y]],dfsn[y]);
            y=fa[top[y]];
        }
    }
    if (dep[x]>dep[y])
        ans+=query(dfsn[y],dfsn[x]);
    else
        ans+=query(dfsn[x],dfsn[y]);
    return ans;
}
void update_subtree(int x,int z)
{
    update(dfsn[x],madfsn[x],z);
}
int query_subtree(int x)
{
    return query(dfsn[x],madfsn[x]);
}
int main(){
    cin>>N>>M>>R>>P;
    top[R]=R;
    for(int i=1;i<=N;i++){
        cin>>B[i];
    }
    for(int i=1;i<N;i++){
        int x,y;
        cin>>x>>y;
        edges[x].push_back(y);
        edges[y].push_back(x);
    }
    cnt=0;
    dfs1(R);
    dfs2(R);
    cnt=1;
    for(int i=1;i<=N;i++){
        A[dfsn[i]]=B[i];
    }
    build();
}
2020/12/19 16:04
加载中...