HNOI2015 接水果

题意：

给你一棵个点的树和条路径，每条路径都有一个权值。

有k组询问，每次询问给你一条路径和一个值。

问你被这条路径包含的所有路径中的第K小的路径的值

题解：

我用的是树上莫队+平衡树(或分块)的方法

平衡树的话是,分块的话就是

稍微口胡一下树上莫队：

把一颗树的欧拉序搞出来，对于查询的两点（假设入栈早）。

如果是一条链，

否则,,同时莫队是要加入

平衡树有什么用？

我们看到题目中求第K大的值，就想到了用平衡树来维护值。

因为平衡树支持插入，删除和查找K大值，和莫队很配。

但其实分块更加优，分块能更好的和莫队配合。

因为分块的插入，查询，总的复杂度是(n，m同阶)

现在要处理的就是如何判断一条路径被包含，或者不被包含。

我们把每条路径看成两个点，如果这两个点都被包含，那么这条路径就是被包含的。

我们只要在莫队时记录一下每条路径两个端点被包含的个数即可。

由于同一个点可能是多条路径的端点，所以我们对每个点建一个vector，

我口胡一下分块的做法，因为更优（我一开始没想到）

先离散化，原来把值x插入平衡树（求第K大），现在就插入值域分块,

查询第K大，分块可以求出。

直接扫每一个块，扫到第一个 个数>=K的那个块停下来，再在块内暴力找。

代码：

（平衡树）

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
#define re register
int n,m,k,l,r,top,t,len;
int root,ncnt,fa[N*5],size[N*5],cnt[N*5],val[N*5],ch[N*5][2];
int a[N],ru[N],chu[N],rev[N],head[N],Ans[N],gs[N],used[N],f[N][20];
struct node{
    int l,r,id,lca,k;
}q[N];
struct node2{
    int too,next;
}edge[N];
vector<int>v[N];
char buf[1<<21],*p1=buf,*p2=buf;
inline int gc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}
inline int read()
{
    int ret=0,f=0;char c=gc();
    while(!isdigit(c)){if(c=='-')f=1;c=gc();}
    while(isdigit(c)){ret=ret*10+c-48;c=gc();}
    if(f)return -ret;return ret;
}
void write(int x){
    if(x>=10) write(x/10);
    putchar(x%10+48);
}
inline void writeln(int x){
    write(x);
    putchar('\n');
}
inline bool chk(int x)
{
    return ch[fa[x]][1]==x;
}
inline void pushup(int x)
{
    size[x]=size[ch[x][0]]+size[ch[x][1]]+cnt[x];
}
inline void Zhuan(int x)
{
    int y=fa[x],z=fa[y],k=chk(x),w=ch[x][k^1];
    ch[y][k]=w;
    fa[w]=y;
    ch[z][chk(y)]=x;
    fa[x]=z;
    ch[x][k^1]=y;
    fa[y]=x;
    pushup(y);pushup(x);
}
inline void splay(int x,int gen=0)
{
    while(fa[x]!=gen)
    {
        int y=fa[x],z=fa[y];
        if(z!=gen)
        {
            if(chk(x)==chk(y))Zhuan(y);
            else Zhuan(x);
        }
        Zhuan(x);
    }
    if(!gen)root=x;
}
inline void insert(int x)
{
    int u=root,p=0;
    while(u&&val[u]!=x)
    {
        p=u;
        u=ch[u][x>val[u]];
    }
    if(u)cnt[u]++;
    else{
        u=++ncnt;
        fa[u]=p;
        ch[p][x>val[p]]=u;
        ch[u][0]=ch[u][1]=0;
        size[u]=cnt[u]=1;
        val[u]=x;
    }
    splay(u);
}
inline int kth(int x)
{
    int u=root;
    while(true)
    {
        if(ch[u][0]&&x<=size[ch[u][0]])u=ch[u][0];
        else if(x>size[ch[u][0]]+cnt[u])
        {
            x-=size[ch[u][0]]+cnt[u];
            u=ch[u][1];
        }
        else return u;
    }
}
inline void find(int x)
{
    int u=root;
    while(x!=val[u]&&ch[u][x>val[u]])u=ch[u][x>val[u]];
    splay(u);
}
inline int pre(int x)
{
    find(x);
    if(val[root]<x)return root;
    int u=ch[root][0];
    while(ch[u][1])u=ch[u][1];
    return u;
}
inline int nxt(int x)
{
    find(x);
    if(val[root]>x)return root;
    int u=ch[root][1];
    while(ch[u][0])u=ch[u][0];
    return u;
}
inline void Delete(int x)
{
    int last=pre(x),next=nxt(x);
    splay(last);
    splay(next,last);
    int del=ch[next][0];
    if(cnt[del]>1)
    {
        cnt[del]--;
        splay(del);
    }
    else ch[next][0]=0;
}
inline void add(int a,int b)
{
    edge[++top].too=b;edge[top].next=head[a];head[a]=top;
}
void dfs(int u,int fa)
{
    ru[u]=++t;rev[t]=u;
    f[u][0]=fa;
    for(re int i=head[u];i;i=edge[i].next)
    {
        int v=edge[i].too;
        if(v==fa)continue;
        dfs(v,u);
    }
    chu[u]=++t;rev[t]=u;
}
inline bool pd(int a,int b)
{
    if((ru[b]<=ru[a])&&(chu[b]>=chu[a]))return true;
    return false;
}
inline int LCA(int x,int y)
{
    if(pd(x,y))return y;
    if(pd(y,x))return x;
    int k=x;
    for(re int j=17;j>=0;j--)
        if((f[k][j]>0)&&(pd(y,f[k][j])==false))k=f[k][j];
    return f[k][0];
}
inline bool cmp(node a,node b)
{
    return ((a.l/len)^(b.l/len))?(a.l<b.l):((a.l/len)&1)?(a.r<b.r):(a.r>b.r);
}
inline void add(int x)
{
    for(re int i=0;i<v[x].size();i++)
    {
        gs[v[x][i]]++;
        if(gs[v[x][i]]==2)insert(a[v[x][i]]);
    }
}
inline void del(int x)
{
    for(re int i=0;i<v[x].size();i++)
    {
        gs[v[x][i]]--;
        if(gs[v[x][i]]==1)Delete(a[v[x][i]]);
    }
}
inline void Add(int x)
{
    if(used[x])del(x);
    else add(x);
    used[x]^=1;
}
int main()
{
    n=read();m=read();k=read();
    for(re int i=1;i<n;i++)
    {
        int x=read(),y=read();
        add(x,y);add(y,x);
    }
    for(re int i=1;i<=m;i++)
    {
        int x=read(),y=read();
        a[i]=read();
        v[x].push_back(i);
        v[y].push_back(i);
    }
    dfs(1,0);
    for(re int i=1;i<=17;i++)
        for(re int j=1;j<=n;j++)
            f[j][i]=f[f[j][i-1]][i-1];
    len=sqrt(n);
    for(re int i=1;i<=k;i++)
    {
        q[i].id=i;
        int x=read(),y=read();
        q[i].k=read();
        if(ru[x]>ru[y])swap(x,y);
        int lca=LCA(x,y);
        if(lca==x)q[i].l=ru[x],q[i].r=ru[y],q[i].lca=0;
        else q[i].l=chu[x],q[i].r=ru[y],q[i].lca=lca;
    }
    sort(q+1,q+k+1,cmp);
    l=1;insert(1e9+1);insert(-1e9-1);
    for(re int i=1;i<=k;i++)
    {
        while(l>q[i].l){l--;Add(rev[l]);}
        while(r<q[i].r){r++;Add(rev[r]);}
        while(l<q[i].l){Add(rev[l]);l++;}
        while(r>q[i].r){Add(rev[r]);r--;}
        if(q[i].lca)Add(q[i].lca);
        Ans[q[i].id]=val[kth(q[i].k+1)];
        if(q[i].lca)Add(q[i].lca);
    }
    for(int i=1;i<=k;i++)writeln(Ans[i]);
    return 0;
}

（分块）

// luogu-judger-enable-o2
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
#define re register
int n,m,k,l,r,top,t,len;
int root,ncnt,size,num,xu[N],sum[N],bel[N],L[N],R[N],b[N];
int a[N],ru[N],chu[N],rev[N],head[N],Ans[N],gs[N],used[N],f[N][20];
struct node{
    int l,r,id,lca,k;
}q[N];
struct node2{
    int too,next;
}edge[N];
vector<int>v[N];
//char buf[1<<21],*p1=buf,*p2=buf;
//inline int gc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}
#define gc getchar
inline int read()
{
    int ret=0,f=0;char c=gc();
    while(!isdigit(c)){if(c=='-')f=1;c=gc();}
    while(isdigit(c)){ret=ret*10+c-48;c=gc();}
    if(f)return -ret;return ret;
}
void write(int x){
    if(x>=10) write(x/10);
    putchar(x%10+48);
}
inline void writeln(int x){
    write(x);
    putchar('\n');
}
inline void insert(int x)
{
    xu[x]++;sum[bel[x]]++;
}
inline void Delete(int x)
{
    xu[x]--;sum[bel[x]]--;
}
inline void add(int a,int b)
{
    edge[++top].too=b;edge[top].next=head[a];head[a]=top;
}
void dfs(int u,int fa)
{
    ru[u]=++t;rev[t]=u;
    f[u][0]=fa;
    for(re int i=head[u];i;i=edge[i].next)
    {
        int v=edge[i].too;
        if(v==fa)continue;
        dfs(v,u);
    }
    chu[u]=++t;rev[t]=u;
}
inline bool pd(int a,int b)
{
    if((ru[b]<=ru[a])&&(chu[b]>=chu[a]))return true;
    return false;
}
inline int LCA(int x,int y)
{
    if(pd(x,y))return y;
    if(pd(y,x))return x;
    int k=x;
    for(re int j=17;j>=0;j--)
        if((f[k][j]>0)&&(pd(y,f[k][j])==false))k=f[k][j];
    return f[k][0];
}
inline bool cmp(node a,node b)
{
    return ((a.l/len)^(b.l/len))?(a.l<b.l):((a.l/len)&1)?(a.r<b.r):(a.r>b.r);
}
inline void add(int x)
{
    for(re int i=0;i<v[x].size();i++)
    {
        gs[v[x][i]]++;
        if(gs[v[x][i]]==2)insert(a[v[x][i]]);
    }
}
inline void del(int x)
{
    for(re int i=0;i<v[x].size();i++)
    {
        gs[v[x][i]]--;
        if(gs[v[x][i]]==1)Delete(a[v[x][i]]);
    }
}
inline void Add(int x)
{
    if(used[x])del(x);
    else add(x);
    used[x]^=1;
}
inline int query(int x)
{
    int i,S=0;
    for(i=1;i<=num;i++)
    {
        S+=sum[i];
        if(S>=x)break;
    }
    for(int j=R[i];j>=L[i];j--)
    {
        if(S>x-xu[j]&&S<=x)return b[j];
        S-=xu[j];
    }
}
int main()
{
    n=read();m=read();k=read();
    for(re int i=1;i<n;i++)
    {
        int x=read(),y=read();
        add(x,y);add(y,x);
    }
    for(re int i=1;i<=m;i++)
    {
        int x=read(),y=read();
        a[i]=b[i]=read();
        v[x].push_back(i);
        v[y].push_back(i);
    }
    sort(b+1,b+m+1);
    size=unique(b+1,b+m+1)-b-1;
    for(int i=1;i<=m;i++)a[i]=lower_bound(b+1,b+size+1,a[i])-b;
    int sz=sqrt(m);
    num=m/sz;
    if(m%sz)num++;
    for(int i=1;i<=m;i++)L[i]=m+1;
    for(int i=1;i<=m;i++)
    {
        bel[i]=(i-1)/sz+1;
        L[bel[i]]=min(L[bel[i]],i);
        R[bel[i]]=max(R[bel[i]],i);
    }
    dfs(1,0);
    for(re int i=1;i<=17;i++)
        for(re int j=1;j<=n;j++)
            f[j][i]=f[f[j][i-1]][i-1];
    len=sqrt(n);
    for(re int i=1;i<=k;i++)
    {
        q[i].id=i;
        int x=read(),y=read();
        q[i].k=read();
        if(ru[x]>ru[y])swap(x,y);
        int lca=LCA(x,y);
        if(lca==x)q[i].l=ru[x],q[i].r=ru[y],q[i].lca=0;
        else q[i].l=chu[x],q[i].r=ru[y],q[i].lca=lca;
    }
    sort(q+1,q+k+1,cmp);
    l=1;
    for(re int i=1;i<=k;i++)
    {
        while(l>q[i].l){l--;Add(rev[l]);}
        while(r<q[i].r){r++;Add(rev[r]);}
        while(l<q[i].l){Add(rev[l]);l++;}
        while(r>q[i].r){Add(rev[r]);r--;}
        if(q[i].lca)Add(q[i].lca);
        Ans[q[i].id]=query(q[i].k);
        if(q[i].lca)Add(q[i].lca);
    }
    for(int i=1;i<=k;i++)writeln(Ans[i]);
    return 0;
}
xuxuxuxuxu 文章被收录于专栏

信息学竞赛

全部评论
%%%
点赞 回复 分享
发布于 2019-10-15 20:36

相关推荐

11-22 17:37
已编辑
江西省吉水县第二中学 Java
点赞 评论 收藏
分享
11-24 14:20
北京大学 Java
秋招offer比较，头部大厂or明星初创
决赛圈了，希望各位前辈能帮忙斟酌一下，n∈[32k，35k]，m∈[10w，13w]&nbsp;字节：n×15&nbsp;+&nbsp;m期权&nbsp;+&nbsp;15w签字费&nbsp;初创：(n+7k)×16&nbsp;+&nbsp;2m期权&nbsp;+&nbsp;15w签字费&nbsp;1优点，字节算挺有诚意，本来确定要去了，但下面的初创给了个大的。毫无疑问title对未来跳槽帮助大&nbsp;1缺点，这个组的人才密度比较大，有一半多是top2的，晋升感觉无望，但跟着大佬多学点东西也还行。&nbsp;2优点:给的钱多，明星初创有一定前景?(几率很小)&nbsp;2缺点:加班比字节还严重。以及这类型公司跳槽，&nbsp;title的...
Echo.Hou：虽然我没去大厂，但是待过俩家初创，我的感觉是厉害的初创很舍得给钱，也很看你的产出，产出不行直接把你开了。当然大厂也可能有这个问题。建议还是去大厂，如果被裁员了最起码还有大厂的title，这年头不确定的事儿太多了。
字节求职进展汇总 软开人，秋招你打算投哪些公司呢
点赞 评论 收藏
分享
10-21 17:38
桂林理工大学 Java
秋招现状
霁华Tel：秋招结束了，好累。我自编了一篇对话，语言别人看不懂，我觉得有某种力量在控制我的身体，我明明觉得有些东西就在眼前，但身边的人却说啥也没有，有神秘人通过电视，手机等在暗暗的给我发信号，我有时候会突然觉得身体的某一部分不属于我了。面对不同的人或场合，我表现出不一样的自己，以至于都不知道自己到底是什么样子的人。我觉得我已经做的很好，不需要其他人的建议和批评，我有些时候难以控制的兴奋，但是呼吸都让人开心。
点赞 评论 收藏
分享
10-19 15:00
文华学院 嵌入式工程师
嵌入式岗位，求大佬指点一下， #找不到工作啊#
粗心的雪碧不放弃：纯学历问题，我这几个月也是一直优化自己的简历，后来发现优化到我自己都觉得牛逼的时候，发现面试数量也没有提升，真就纯学历问题
点赞 评论 收藏
分享
11-24 23:07
Momenta_算法
Momenta入职感受
给大家详细聊一聊公司上班细节，大家可以评估下自己来了能否适应。智驾整体强度都比较大，因为基本都算初创公司，还没做到能躺着收钱的地步，凡事看两面，压力大但是能学到东西，不至于说每天干重复的东西么没有提示，工作时间10am-19pm，项目交付的时候加班就多，基本上9点左右，公司包三餐&nbsp;工作再忙都要好好吃饭&nbsp;公司统一使用美餐app&nbsp;可以根据自己喜好来订餐到工位餐区也可以去楼下美好荟去合作商家堂食比如：老乡鸡&nbsp;costa&nbsp;美餐20元餐标超出部分自己补差价👇&nbsp;王阿吉的快餐真的很好吃强推&nbsp;）别担心会吃腻&nbsp;行政小姐姐会定期更换合作商家。其他福利&nbsp;，中秋节有公司定制周边和礼盒（全年就中秋有），出行方面内部员...
Momenta公司福利 286人发布
点赞 评论 收藏
分享
1 收藏 评论
分享

全站热榜

正在热议
# 25届秋招总结 #
322333次浏览 2990人参与
# 上班苦还是上学苦呢？ #
69713次浏览 615人参与
# 阿里云管培生offer #
36305次浏览 420人参与
# 地方国企笔面经互助 #
4397次浏览 12人参与
# 如果有时光机，你最想去到哪个年纪？ #
20573次浏览 349人参与
# 选完offer后，你后悔学本专业吗 #
21498次浏览 155人参与
# 百度开奖 #
179807次浏览 1126人参与
# 如何一边实习一边秋招 #
995783次浏览 12661人参与
# 我的实习求职记录 #
6067157次浏览 83521人参与
# 招聘要求与实际实习内容不符怎么办 #
10674次浏览 276人参与
# 入职第一天，你准备什么时候下班 #
21485次浏览 144人参与
# 许愿池 #
214521次浏览 2534人参与
# bilibili求职进展汇总 #
32864次浏览 354人参与
# 学历or实习经历，哪个更重要 #
53458次浏览 417人参与
# 实习工作，你找得还顺利吗？ #
247535次浏览 2902人参与
# 海康威视求职进展汇总 #
400319次浏览 3407人参与
# 通信硬件薪资爆料 #
607311次浏览 5150人参与
# 正在实习的你，几点下班 #
52974次浏览 395人参与
# 如果再来一次，你还会学硬件吗 #
95063次浏览 1169人参与
# 工作两年想退休了 #
52949次浏览 672人参与
# 软件开发薪资爆料 #
2191890次浏览 21874人参与
# 我的失利项目复盘 #
668104次浏览 11247人参与
牛客网
牛客企业服务