2019南昌网络赛 J Distance on the tree 主席树+lca

题意

给一颗树,每条边有边权,每次询问\(u\)\(v\)的路径中有多少边的边权小于等于\(k​\)

分析

在树的每个点上建\(1​\)\(i​\)的权值线段树,查询的时候同时跑\(u,v,lca(u,v)​\)三个版本的线段树,查询\(1​\)\(k​\)的树上差分和\(val[u]+val[v]-2*val[lca]​\)

Code

#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
using namespace std;
typedef long long ll;
const int inf=1e9;
const int maxn=2e5+10;
int n,m,q;
int a[maxn],b[maxn];
typedef pair<int,int> pii;
vector<pii>g[maxn];
int top[maxn],sz[maxn],f[maxn],son[maxn],d[maxn];
int val[maxn*30],ls[maxn*30],rs[maxn*30],rt[maxn],tot;
int qu[maxn],qv[maxn],qk[maxn];
void bd(int l,int r,int &p){
    val[++tot]=val[p],ls[tot]=ls[p],rs[tot]=rs[p],p=tot;
    if(l==r) return;int mid=l+r>>1;
    bd(l,mid,ls[p]);bd(mid+1,r,rs[p]);
}
void up(int k,int l,int r,int &p){
    val[++tot]=val[p]+1,ls[tot]=ls[p],rs[tot]=rs[p],p=tot;
    if(l==r) return;int mid=l+r>>1;
    if(k<=mid) up(k,l,mid,ls[p]);
    else up(k,mid+1,r,rs[p]);
}
int qy(int k,int l,int r,int a,int b,int c){
    int ret=0;
    if(l>=1&&r<=k) return val[a]+val[b]-2*val[c];
    int mid=l+r>>1;
    if(1<=mid) ret+=qy(k,l,mid,ls[a],ls[b],ls[c]);
    if(k>mid) ret+=qy(k,mid+1,r,rs[a],rs[b],rs[c]);
    return ret;
}
void add(int x){
    int k=lower_bound(b+1,b+m+1,a[x])-b;
    rt[x]=rt[f[x]];up(k,1,m,rt[x]);
}
void dfs1(int u){
    sz[u]=1;d[u]=d[f[u]]+1;add(u);
    for(pii x:g[u]){
        if(x.fi==f[u]) continue;
        a[x.fi]=x.se;f[x.fi]=u;
        dfs1(x.fi);sz[u]+=sz[x.fi];
        if(sz[x.fi]>sz[son[u]]) son[u]=x.fi;
    }
}
void dfs2(int u,int t){
    top[u]=t;
    if(!son[u]) return;
    dfs2(son[u],t);
    for(pii x:g[u]){
        if(x.fi==son[u]||x.fi==f[u]) continue;
        dfs2(x.fi,x.fi);
    }
}
int lca(int x,int y){
    while(top[x]!=top[y]){
        if(d[top[x]]>=d[top[y]]) x=f[top[x]];
        else y=f[top[y]];
    }
    if(d[x]>=d[y]) return y;
    else return x;
}
int main(){
    scanf("%d%d",&n,&q);
    for(int i=1,a,x,c;i<n;i++){
        scanf("%d%d%d",&a,&x,&c);
        b[++m]=c;
        g[a].pb(pii(x,c));
        g[x].pb(pii(a,c));
    }
    for(int i=1;i<=q;i++){
        scanf("%d%d%d",&qu[i],&qv[i],&qk[i]);
        b[++m]=qk[i];
    }
    sort(b+1,b+m+1);
    m=unique(b+1,b+m+1)-b-1;
    bd(1,m,rt[0]);
    dfs1(1);dfs2(1,1);
    for(int i=1;i<=q;i++){
        qk[i]=lower_bound(b+1,b+m+1,qk[i])-b;
        printf("%d\n",qy(qk[i],1,m,rt[qu[i]],rt[qv[i]],rt[lca(qu[i],qv[i])]));
    }
    return 0;
}
全部评论

相关推荐

07-09 18:33
门头沟学院 Java
这么逆天每年都有人去???&nbsp;填多益网申就是大型的服从性测试
鲁大牛:辅导员在群里发了这个公司我就申了一下。网申居然要写当场开摄像头写两篇不少于三百字的作文。太逆天了
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-09 12:10
直接上图
牛客13578115...:改得一般,不值80
点赞 评论 收藏
分享
强大的马里奥:不太可能,我校计算机硕士就业率99%
点赞 评论 收藏
分享
来个大佬救一下,为上投了都是石沉大海了,没实习经历的话怕秋招直接进不了面。什么实习这么难找,基本
心态爆炸了:现在正式的岗位都少,实习基本不咋招的,除了大厂,中小企业其实没那么多岗位需求,就算是有,大多都是招一两个廉价劳动力,同时,他们也会希望你一来就能干活的,没时间培训你,就让你了解公司的项目,你了解完就可以开始干活。再者是,很多低质量的实习其实用处没有那么大的。我去年也是找实习找到破防,最后去了一家深圳的小公司实习,工作对我来说很简单,甚至不如我在学校做的项目,秋招的时候,这段实习经历也并没有帮上什么忙,投递简历,依旧非常低的回复率。低回复率是常态,尤其是找实习,找不到,那就把重心放在优化自己的简历和项目,多看八股文,锻炼自己的面试能力,多看别人的面经,自己模拟面试,等秋招的时候,只要有那么寥寥几次,好好抓住那几次机会。
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务