【BZOJ4009】【HNOI2015】接水果

为什么这一道题被权限了啊好气啊

题意就是，先给你若干条链，然后每次给你一条链问之前给的那些链里面是它子链的权值第\(k\)小的是多少。

可以想到，如果一条链是另一条的子链，那么可以按是否有一个点是另一个点父亲分两种情况。

那么我们写出对父链的约束条件，可以发现是一个类似矩阵的东西。

即把问题转化为：先给你若干个矩阵，每次问你覆盖某个点的矩阵中权值第\(k\)小的是多少。

于是用整体二分。计算点在多少矩阵内用扫描线+树状数组。

// <4009.cpp> - Tue Feb 21 17:55:16 2017
// This file is created by XuYike's black technology automatically.
// Copyright (C) 2015 ChangJun High School, Inc.
// I don't know what this program is.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long lol;
#define next nxt
#define end edn
template<typename T>
inline void gg(T &res){
    res=0;T fh=1;char ch=getchar();
    while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();
    if(ch=='-')fh=-1,ch=getchar();
    while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();
    res*=fh;
}
inline int gi(){int x;gg(x);return x;}
inline lol gl(){lol x;gg(x);return x;}
const int MAXN=40010;
const int MAXM=80010;
const int K=17;
const int INF=1e9;
int bt,b[MAXN],next[MAXM],to[MAXM],val[MAXM];
inline void add(int x,int y,int z=0){
    next[++bt]=b[x];b[x]=bt;to[bt]=y;val[bt]=z;
    next[++bt]=b[y];b[y]=bt;to[bt]=x;val[bt]=z;
}
int dt,dfn[MAXN],end[MAXN],f[K][MAXN],dep[MAXN];
void dfs(int x){
    dfn[x]=++dt;
    for(int i=b[x];i;i=next[i]){
        if(to[i]==f[0][x])continue;
        f[0][to[i]]=x; 
        dep[to[i]]=dep[x]+1;
        dfs(to[i]);
    }
    end[x]=dt;
}
int lca(int x,int y){
    if(dep[x]<dep[y])swap(x,y);
    int d=dep[x]-dep[y];
    for(int i=0,p=1;i<K;i++,p<<=1)
        if(d&p)x=f[i][x];
    if(x==y)return x;
    for(int i=K-1;i>=0;i--){
        if(f[i][x]==f[i][y])continue;
        x=f[i][x];y=f[i][y];
    }
    return f[0][x];
}
struct matrix{
    int lx,rx,ly,ry,v;
    bool operator <(const matrix b) const{return v<b.v;}
}t[MAXM];
struct query{
    int x,y,k,id;
    bool operator <(const query b) const{return x<b.x;}
}q[MAXN],ql[MAXN],qr[MAXN];
struct eve{
    int t,p,x;
    bool operator <(const eve b) const{return t<b.t;}
}e[MAXN<<3];
int n,c[MAXN];
inline void mod(int x,int y){for(;x<=n;x+=x&-x)c[x]+=y;}
inline int get(int x){
    int res=0;
    for(;x;x-=x&-x)res+=c[x];
    return res;
}
int ans[MAXN];
void work(int L,int R,int l,int r){
    if(L>R)return;
    if(l==r){
        for(int i=L;i<=R;i++)ans[q[i].id]=t[l].v;
        return;
    }
    int m=l+r>>1,et=0;
    for(int i=l;i<=m;i++){
        e[++et]=(eve){t[i].lx,t[i].ly,1};
        e[++et]=(eve){t[i].lx,t[i].ry+1,-1};
        e[++et]=(eve){t[i].rx+1,t[i].ly,-1};
        e[++et]=(eve){t[i].rx+1,t[i].ry+1,1};
    }
    sort(e+1,e+et+1);
    int p=1,lt=0,rt=0;
    for(int i=L;i<=R;i++){
        for(;p<=et&&e[p].t<=q[i].x;p++)mod(e[p].p,e[p].x);
        int nk=get(q[i].y);
        if(q[i].k<=nk)ql[lt++]=q[i];
        else{q[i].k-=nk;qr[rt++]=q[i];}
    }
    for(;p<=et;p++)mod(e[p].p,e[p].x);
    for(int i=0;i<lt;i++)q[L+i]=ql[i];
    for(int i=0;i<rt;i++)q[L+lt+i]=qr[i];
    work(L,L+lt-1,l,m);
    work(L+lt,R,m+1,r);
}
int main(){
    n=gi();int P=gi(),Q=gi();
    for(int i=1;i<n;i++)add(gi(),gi());
    dfs(1);
    for(int j=1;j<K;j++)
        for(int i=1;i<=n;i++)f[j][i]=f[j-1][f[j-1][i]];
    int mt=0;
    for(int i=1;i<=P;i++){
        int x=gi(),y=gi(),z=gi(),L=lca(x,y);
        if(dfn[x]>dfn[y])swap(x,y);
        if(L==x){
            int d=dep[y]-dep[x]-1,w=y;
            for(int i=0,p=1;i<K;i++,p<<=1)if(d&p)w=f[i][w];
            t[++mt]=(matrix){1,dfn[w]-1,dfn[y],end[y],z};
            t[++mt]=(matrix){dfn[y],end[y],end[w]+1,n,z};
        }else t[++mt]=(matrix){dfn[x],end[x],dfn[y],end[y],z};
    }
    sort(t+1,t+mt+1);
    for(int i=1;i<=Q;i++){
        q[i].x=dfn[gi()],q[i].y=dfn[gi()],q[i].k=gi(),q[i].id=i;
        if(q[i].x>q[i].y)swap(q[i].x,q[i].y);
    }
    sort(q+1,q+Q+1);
    work(1,Q,1,mt);
    for(int i=1;i<=Q;i++)printf("%d\n",ans[i]);
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

// <4009.cpp> - Tue Feb 21 17:55:16 2017

// This file is created by XuYike's black technology automatically.

// I don't know what this program is.

#include <iostream>

#include <vector>

#include <algorithm>

#include <cstring>

#include <cstdio>

#include <cmath>

using namespace std;

typedef long long lol;

#define next nxt

#define end edn

template<typename T>

inline void gg(T &res){

res=0;T fh=1;char ch=getchar();

while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();

if(ch=='-')fh=-1,ch=getchar();

while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();

res*=fh;

}

inline int gi(){int x;gg(x);return x;}

inline lol gl(){lol x;gg(x);return x;}

const int MAXN=40010;

const int MAXM=80010;

const int K=17;

const int INF=1e9;

int bt,b[MAXN],next[MAXM],to[MAXM],val[MAXM];

inline void add(int x,int y,int z=0){

next[++bt]=b[x];b[x]=bt;to[bt]=y;val[bt]=z;

next[++bt]=b[y];b[y]=bt;to[bt]=x;val[bt]=z;

}

int dt,dfn[MAXN],end[MAXN],f[K][MAXN],dep[MAXN];

void dfs(int x){

dfn[x]=++dt;

for(int i=b[x];i;i=next[i]){

if(to[i]==f[0][x])continue;

f[0][to[i]]=x;

dep[to[i]]=dep[x]+1;

dfs(to[i]);

}

end[x]=dt;

}

int lca(int x,int y){

if(dep[x]<dep[y])swap(x,y);

int d=dep[x]-dep[y];

for(int i=0,p=1;i<K;i++,p<<=1)

if(d&p)x=f[i][x];

if(x==y)return x;

for(int i=K-1;i>=0;i--){

if(f[i][x]==f[i][y])continue;

x=f[i][x];y=f[i][y];

}

return f[0][x];

}

struct matrix{

int lx,rx,ly,ry,v;

bool operator <(const matrix b) const{return v<b.v;}

}t[MAXM];

struct query{

int x,y,k,id;

bool operator <(const query b) const{return x<b.x;}

}q[MAXN],ql[MAXN],qr[MAXN];

struct eve{

int t,p,x;

bool operator <(const eve b) const{return t<b.t;}

}e[MAXN<<3];

int n,c[MAXN];

inline void mod(int x,int y){for(;x<=n;x+=x&-x)c[x]+=y;}

inline int get(int x){

int res=0;

for(;x;x-=x&-x)res+=c[x];

return res;

}

int ans[MAXN];

void work(int L,int R,int l,int r){

if(L>R)return;

if(l==r){

for(int i=L;i<=R;i++)ans[q[i].id]=t[l].v;

return;

}

int m=l+r>>1,et=0;

for(int i=l;i<=m;i++){

e[++et]=(eve){t[i].lx,t[i].ly,1};

e[++et]=(eve){t[i].lx,t[i].ry+1,-1};

e[++et]=(eve){t[i].rx+1,t[i].ly,-1};

e[++et]=(eve){t[i].rx+1,t[i].ry+1,1};

}

sort(e+1,e+et+1);

int p=1,lt=0,rt=0;

for(int i=L;i<=R;i++){

for(;p<=et&&e[p].t<=q[i].x;p++)mod(e[p].p,e[p].x);

int nk=get(q[i].y);

if(q[i].k<=nk)ql[lt++]=q[i];

else{q[i].k-=nk;qr[rt++]=q[i];}

}

for(;p<=et;p++)mod(e[p].p,e[p].x);

for(int i=0;i<lt;i++)q[L+i]=ql[i];

for(int i=0;i<rt;i++)q[L+lt+i]=qr[i];

work(L,L+lt-1,l,m);

work(L+lt,R,m+1,r);

}

int main(){

n=gi();int P=gi(),Q=gi();

for(int i=1;i<n;i++)add(gi(),gi());

dfs(1);

for(int j=1;j<K;j++)

for(int i=1;i<=n;i++)f[j][i]=f[j-1][f[j-1][i]];

int mt=0;

for(int i=1;i<=P;i++){

int x=gi(),y=gi(),z=gi(),L=lca(x,y);

if(dfn[x]>dfn[y])swap(x,y);

if(L==x){

int d=dep[y]-dep[x]-1,w=y;

for(int i=0,p=1;i<K;i++,p<<=1)if(d&p)w=f[i][w];

t[++mt]=(matrix){1,dfn[w]-1,dfn[y],end[y],z};

t[++mt]=(matrix){dfn[y],end[y],end[w]+1,n,z};

}else t[++mt]=(matrix){dfn[x],end[x],dfn[y],end[y],z};

}

sort(t+1,t+mt+1);

for(int i=1;i<=Q;i++){

q[i].x=dfn[gi()],q[i].y=dfn[gi()],q[i].k=gi(),q[i].id=i;

if(q[i].x>q[i].y)swap(q[i].x,q[i].y);

}

sort(q+1,q+Q+1);

work(1,Q,1,mt);

for(int i=1;i<=Q;i++)printf("%d\n",ans[i]);

return 0;

}