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;
}
全部评论

相关推荐

序&nbsp;朋友们,好久不见。&nbsp;笔者在过去消失的五个月里被困在情绪牢笼中过的相当煎熬,一度丢失自己,觉得整个世界都是昏暗的。&nbsp;庆幸的是靠着自己纯硬扛也是走出来了。表达欲再度回归,所以真的很开心还有机会能在再和大家见面。&nbsp;破碎秋招&nbsp;抑郁情绪的引爆点必然是秋招期间遭受的打击了,从去年九月份腾讯转正被告知失败之后就开始疯狂投递简历,每天都在经历:简历挂、一面挂、二面挂、三面挂、HR面挂,每天睁开眼就被无所适从的挫败感包围。&nbsp;秋招的特点是即便流程走到最后一步也不一定会&nbsp;offer,因为还需要进入大池子进行横向对比,俗称泡池子,而这一泡我的大多数面试流程到后面就没了后文,这一度让我感觉非常绝望。我深知自己学历并...
SoNiC_X:我已经工作快2年了,当时高考没考好没去到想去的学校,觉得天要塌了;校招找不到工作,觉得天要塌了;现在工作觉得看不到未来,觉得天要塌了;最近最大的感悟就是:天会一直塌,但是生活也会一直继续下去,还是要调整好自己的心态,不要因为一时的困难把自己困住,要记住完蛋的日子永远在后头
点赞 评论 收藏
分享
佛系的本杰明反对画饼:个人看法,实习经历那段是败笔,可以删掉,它和你目标岗位没什么关系,没有用到什么专业技能,甚至会降低你项目经历内容的可信度。个人技能那里可以再多写一点,去boss直聘上看别人写的岗位要求,可以把你会的整合一下,比如熟悉常规的开关电源拓扑结构(BUCK、正激、反激、LLC等),熟悉常用的通信总线协议和通信接口,如UART,IIC,SPI等。简历首先是HR看的,HR大多不懂技术,会从简历里去找关键字,你没有那些关键字他可能就把你筛掉了,所以个人技能尽量针对着岗位描述写一下。还有电赛获佳绩,获奖了就写什么奖,没获奖就把获佳绩删了吧,要不会让人感觉夸大。
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务