当且仅当盘的途径是鲜果之门径的子路径(例如。当且仅当盘的门道是鲜果之路子的子路径(例如。

4009: [Hnoi2015]接水果

Time Limit: 60 Sec  Memory Limit: 512 MB

4009: [Hnoi2015]接水果

Time Limit: 60 Sec  Memory Limit: 512 MB

Description

风见幽香非常喜爱嬉水一个称
osu!的游艺,其中其无比喜爱玩的模式就是是连接水果。由于它早已DT FC 了The big
black,
她当这游戏太简单了,于是发明了一个尤为不便之版本。首先来一个地图,是均等蔸由
n 个顶、n-1 条边组成的扶植(例如图 1为来之树包含 8 独顶、7
条边)。这颗树上有 P 个盘子,每个盘子实际上是如出一辙修路(例如图 1 遭到极 6
到极限 8 的路子),并且每个盘子还有一个权值。第 i
单盘子就是顶点aiai到顶点bibi的路(由于是养,所以从aiai到bibi 的路线是唯一的), 权值为cici。接下来依次会产生Q独水果掉下来,每个水果本质上吗是同等长长的途径,第i
只水果是打巅峰 uiui 到终端vivi 的路。 
清香每次需要选择一个盘去搭当前之果品:一个盘能接住一个水果,当且仅当盘的途径是水果之门径的子路径(例如
图1遭遇自 3到7 的路线是自从1交8底不二法门的子路径)。 
此地规定:从a 到b的门径和从b到
a的门路是平等长达路线。当然为增强难度,对于第 i
独水果,你用选择会接住她的保有盘子吃,权值第 kiki 小的那个盘子,每个盘子可重复使用(没有使次数之上限:一个盘子接了一个水果后,后面还而继续接其他水果,只要其是水果路径的子路径)。幽香认为此娱乐大不便,你能够轻轻松松解决被其看呢? 

Description

风见幽香非常好玩玩一个名
osu!的游戏,其中其太欣赏玩玩的模式就是是接水果。由于其已DT FC 了The big
black,
她以为这个娱乐太简单了,于是发明了一个一发难以的本。首先发出一个地图,是同株由
n 个极点、n-1 条边组成的培养(例如图 1叫起底培训包含 8 单极点、7
条边)。这颗树上有 P 个盘子,每个盘子实际上是相同漫长路子(例如图 1 着极 6
到终点 8 的门道),并且每个盘子还有一个权值。第 i
独盘子就是顶点aiai到顶点bibi的门径(由于是栽培,所以从aiai到bibi 的门路是唯一的), 权值为cici。接下来依次会发生Q单水果掉下,每个水果本质上为是平久路,第i
独水果是于巅峰 uiui 到巅峰vivi 的路径。 
香每次要选择一个盘去接当前之果品:一个盘能接住一个水果,当且仅当盘的门道是水果之路子的子路径(例如
图1遭遇打 3到7 之门径是自从1交8之门路的子路径)。 
此处规定:从a 到b的路子和从b到
a的途径是平等漫漫路线。当然为增强难度,对于第 i
独水果,你得选择会接住她的保有盘子中,权值第 kiki 小的那个盘子,每个盘子可重复使用(没有用次数的上限:一个盘子接完一个水果后,后面还可连续接其他水果,只要她是水果路径的子路径)。幽香认为是娱乐大不便,你能自在解决吃其圈吗? 

Input

第一实践三个数 n和P
和Q,表示树的轻重以及物价指数的个数与鲜果之个数。 
联网下n-1 行,每行两个数
a、b,表示树上的a和b 之间出一样久边。树被极按1暨 n标号。 
连着下去 P 行,每行三个数
a、b、c,表示路径为 a 到 b、权值为 c 的行情,其中0≤c≤109109,a不顶b。 
连着下Q行,每行三单数 u、v、k,表示路径为 u到 v的水果,其中
u不等于v,你得选择第 k小的行情,第k
小得是。

Input

首先实施三只数 n和P
和Q,表示树的高低与物价指数的个数和鲜果之个数。 
紧接下n-1 行,每行两只数
a、b,表示树上的a和b 之间发生相同漫长边。树被极按1顶 n标号。 
紧接下去 P 行,每行三只数
a、b、c,表示路径为 a 到 b、权值为 c 的物价指数,其中0≤c≤109109,a不顶b。 
紧接下Q行,每行三独数 u、v、k,表示路径也 u到 v的鲜果,其中
u不等于v,你得选择第 k小的盘,第k
小得有。

Output

对每个果子,输出一行表示选择的盘子的权值。

Output

对此每个果子,输出一行表示选择的盘的权值。

Sample Input

10 10 10 
1 2 
2 3 
3 4 
4 5 
5 6 
6 7 
7 8 
8 9 
9 10 
3 2 217394434 
10 7 13022269 
6 7 283254485 
6 8 333042360 
4 6 442139372 
8 3 225045590 
10 4 922205209 
10 8 808296330 
9 2 486331361 
4 9 551176338 
1 8 5 
3 8 3 
3 8 4 
1 8 3 
4 8 1 
2 3 1 
2 3 1 
2 3 1 
2 4 1 
1 4 1

Sample Input

10 10 10 
1 2 
2 3 
3 4 
4 5 
5 6 
6 7 
7 8 
8 9 
9 10 
3 2 217394434 
10 7 13022269 
6 7 283254485 
6 8 333042360 
4 6 442139372 
8 3 225045590 
10 4 922205209 
10 8 808296330 
9 2 486331361 
4 9 551176338 
1 8 5 
3 8 3 
3 8 4 
1 8 3 
4 8 1 
2 3 1 
2 3 1 
2 3 1 
2 4 1 
1 4 1

Sample Output

442139372 
333042360 
442139372 
283254485 
283254485 
217394434 
217394434 
217394434 
217394434 
217394434

Sample Output

442139372 
333042360 
442139372 
283254485 
283254485 
217394434 
217394434 
217394434 
217394434 
217394434

Hint

  我无权力号…因为时限大就是改成权限题真的好吧?

  好像自己为说道不起什么不好的道理。

  这书非常有意思的,对于我这种码废+代码能力差+思维混乱+弱的人头来说,这书挺杀时间之…一个上午即给她跪了。

  啊反正你便是力所能及拿一个盘子变成一个还是简单独矩形?把一个水果变成一个沾?

  然后哪怕是统计覆盖点的权值第k粗的矩形是哪个?

  hin有道理啊我干什么不怕是想念不出来啊吧吧?

  然后一旦您会扫描线的说话
就是一模一样鸣整体二分割裸题了?

  如果非会见之言辞,你早晚会差分是吧…

  把一个矩形按x轴拆成左加右减,树状数组搞来。

  然后即是均等道整体二瓜分裸题了?

  为什么一个个 一百执行还休想的
我却由了如此多呢?

  思维混乱+弱啊!

  注意数组要起两加倍,因为盘子可能有有限个。

#include   <iostream>
#include   <cstdio>
#include    <cstdlib>
#include    <algorithm>
#include    <vector>
#include    <cstring>
#include    <queue>
#include    <complex>
#include    <stack>
#define LL long long int
#define dob double
using namespace std;

const int N = 40010;
struct Node{int to,next;}E[N<<1];
struct Plate{
  int xl,xr,yl,yr,val;
  bool operator <(const Plate &p)const{
    return val<p.val;
  }
}plate[N<<1];
struct Fruit{
  int x,y,k,id;
  bool operator <(const Fruit &f)const{
    return x<f.x;
  }
}fruit[N],que1[N],que2[N];
struct Data{
  int x,l,r,val;
  bool operator <(const Data &l)const{
    return x<l.x;
  }
}Line[N<<1];
int n,P,Q,Ans[N],cnt,head[N],tot;
int fa[21][N],dep[N],size[N],son[N],top[N],dfn[N],tim,last[N];
struct Bit{
  int A[N],vis[N];
  inline int lb(int x){
    return x&-x;
  }
  inline void upd(int x,int val){
    for(;x<=n;x+=lb(x)){
      if(vis[x]!=tim)A[x]=0,vis[x]=tim;
      A[x]+=val;
    }
  }
  inline void update(int l,int r,int val){
    upd(l,val);upd(r+1,-val);
  }
  inline int query(int x,int ans=0){
    for(;x;x-=lb(x)){
      if(vis[x]!=tim)A[x]=0,vis[x]=tim;
      ans+=A[x];
    }
    return ans;
  }
}T;

inline int gi(){
  int x=0,res=1;char ch=getchar();
  while(ch>'9'||ch<'0'){if(ch=='-')res*=-1;ch=getchar();}
  while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
  return x*res;
}

inline void link(int u,int v){
  E[++tot]=(Node){v,head[u]};
  head[u]=tot;
}

inline void join(int x){
  for(int i=1;i<=15;++i)
    fa[i][x]=fa[i-1][fa[i-1][x]];
}

inline void dfs1(int x,int fat){
  fa[0][x]=fat;dep[x]=dep[fat]+1;join(x);
  dfn[x]=++tim;
  for(int e=head[x];e;e=E[e].next){
    int y=E[e].to;if(y==fa[0][x])continue;
    dfs1(y,x);
  }
  last[x]=tim;
}

inline int lca(int x,int y){
  if(x==y)return x;
  if(dep[x]<dep[y])swap(x,y);
  for(int i=15;i>=0;--i)
    if(dep[fa[i][x]]>=dep[y])
      x=fa[i][x];
  if(x==y)return x;
  for(int i=15;i>=0;--i)
    if(fa[i][x]!=fa[i][y])
      x=fa[i][x],y=fa[i][y];
  return fa[0][x];
}

inline int jump(int x,int goal){
  for(int i=15;i>=0;--i)
    if(dep[fa[i][x]]>dep[goal])
      x=fa[i][x];
  return x;
}

/*
  把答案(盘子)二分。
  把左边的矩形加进去。
  然后check,calc一下盘子个数,和k比较一下,划分一下。
  递归处理。
*/

inline void solve(int optl,int optr,int l,int r){
  if(optl>optr || l>r)return;++tim;
  if(optl==optr){
    for(int i=l;i<=r;++i)
      Ans[fruit[i].id]=plate[optl].val;
    return;
  }
  int mid=(optl+optr)>>1,tot1=0,tot2=0,k=l,tmp=0,cnt1=1,cnt2=l;
  for(int i=optl;i<=mid;++i){
    Line[++tmp]=(Data){plate[i].xl,plate[i].yl,plate[i].yr,1};
    Line[++tmp]=(Data){plate[i].xr+1,plate[i].yl,plate[i].yr,-1};
  }
  sort(Line+1,Line+tmp+1);
  while(cnt1<=tmp && cnt2<=r){
    if(Line[cnt1].x<=fruit[cnt2].x){
      int xl=Line[cnt1].l,xr=Line[cnt1].r,val=Line[cnt1].val;
      T.update(xl,xr,val);cnt1++;
    }
    else{
      int sum=T.query(fruit[cnt2].y);
      if(sum>=fruit[cnt2].k)que1[++tot1]=fruit[cnt2++];
      else fruit[cnt2].k-=sum,que2[++tot2]=fruit[cnt2++];
    }
  }
  while(cnt2<=r){
    int sum=T.query(fruit[cnt2].y);
    if(sum>=fruit[cnt2].k)que1[++tot1]=fruit[cnt2++];
    else fruit[cnt2].k-=sum,que2[++tot2]=fruit[cnt2++];
  }
  for(int i=1;i<=tot1;++i)fruit[k++]=que1[i];
  for(int i=1;i<=tot2;++i)fruit[k++]=que2[i];
  solve(optl,mid,l,l+tot1-1);
  solve(mid+1,optr,l+tot1,r);
}

int main()
{
  freopen("fruit_hnoi2015.in","r",stdin);
  freopen("fruit_hnoi2015.out","w",stdout);
  n=gi();P=gi();Q=gi();
  for(int i=1;i<n;++i){
    int u=gi(),v=gi();
    link(u,v);link(v,u);
  }
  dfs1(1,1);
  for(int i=1;i<=P;++i){
    int a=gi(),b=gi(),c=gi(),u=lca(a,b);
    if(dfn[a]>dfn[b])swap(a,b);
    if(u!=a)plate[++cnt]=(Plate){dfn[a],last[a],dfn[b],last[b],c};
    else{
      int v=jump(b,a);
      if(dfn[v]>1)plate[++cnt]=(Plate){1,dfn[v]-1,dfn[b],last[b],c};
      if(last[v]<n)plate[++cnt]=(Plate){dfn[b],last[b],last[v]+1,n,c};
    }
  }
  for(int i=1;i<=Q;++i){
    int a=gi(),b=gi(),k=gi();
    if(dfn[a]>dfn[b])swap(a,b);
    fruit[i]=(Fruit){dfn[a],dfn[b],k,i};
  }
  sort(plate+1,plate+cnt+1);
  sort(fruit+1,fruit+Q+1);
  solve(1,cnt,1,Q);
  for(int i=1;i<=Q;++i)printf("%d\n",Ans[i]);
  return 0;
}

  

 

Hint

  我尚未权力号…因为时限大就是成为权限题真的好啊?

  好像自己呢谈不有什么不好的道理。

  这书很有趣的,对于我这种码废+代码能力差+思维混乱+弱的丁吧,这书挺杀时间之…一个上午便深受她跪了。

  啊反正你虽是力所能及拿一个行情变成一个要个别独矩形?把一个水果变成一个接触?

  然后虽是统计覆盖点的权值第k小之矩形是何许人也?

  hin有道理啊我何以就是是纪念不出来也吗吗?

  然后如果您晤面扫描线的语句
就是同一志整体二分裸题了?

  如果不见面之话语,你势必会差分是吧…

  将一个矩形按x轴拆成左加右减,树状数组搞来。

  然后即使是同等鸣整体二分割裸题了?

  为什么一个个 一百实施且不要的
我可由了这么多吧?

  思维混乱+弱啊!

  注意数组要开两倍,因为盘子可能出三三两两个。

#include   <iostream>
#include   <cstdio>
#include    <cstdlib>
#include    <algorithm>
#include    <vector>
#include    <cstring>
#include    <queue>
#include    <complex>
#include    <stack>
#define LL long long int
#define dob double
using namespace std;

const int N = 40010;
struct Node{int to,next;}E[N<<1];
struct Plate{
  int xl,xr,yl,yr,val;
  bool operator <(const Plate &p)const{
    return val<p.val;
  }
}plate[N<<1];
struct Fruit{
  int x,y,k,id;
  bool operator <(const Fruit &f)const{
    return x<f.x;
  }
}fruit[N],que1[N],que2[N];
struct Data{
  int x,l,r,val;
  bool operator <(const Data &l)const{
    return x<l.x;
  }
}Line[N<<1];
int n,P,Q,Ans[N],cnt,head[N],tot;
int fa[21][N],dep[N],size[N],son[N],top[N],dfn[N],tim,last[N];
struct Bit{
  int A[N],vis[N];
  inline int lb(int x){
    return x&-x;
  }
  inline void upd(int x,int val){
    for(;x<=n;x+=lb(x)){
      if(vis[x]!=tim)A[x]=0,vis[x]=tim;
      A[x]+=val;
    }
  }
  inline void update(int l,int r,int val){
    upd(l,val);upd(r+1,-val);
  }
  inline int query(int x,int ans=0){
    for(;x;x-=lb(x)){
      if(vis[x]!=tim)A[x]=0,vis[x]=tim;
      ans+=A[x];
    }
    return ans;
  }
}T;

inline int gi(){
  int x=0,res=1;char ch=getchar();
  while(ch>'9'||ch<'0'){if(ch=='-')res*=-1;ch=getchar();}
  while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
  return x*res;
}

inline void link(int u,int v){
  E[++tot]=(Node){v,head[u]};
  head[u]=tot;
}

inline void join(int x){
  for(int i=1;i<=15;++i)
    fa[i][x]=fa[i-1][fa[i-1][x]];
}

inline void dfs1(int x,int fat){
  fa[0][x]=fat;dep[x]=dep[fat]+1;join(x);
  dfn[x]=++tim;
  for(int e=head[x];e;e=E[e].next){
    int y=E[e].to;if(y==fa[0][x])continue;
    dfs1(y,x);
  }
  last[x]=tim;
}

inline int lca(int x,int y){
  if(x==y)return x;
  if(dep[x]<dep[y])swap(x,y);
  for(int i=15;i>=0;--i)
    if(dep[fa[i][x]]>=dep[y])
      x=fa[i][x];
  if(x==y)return x;
  for(int i=15;i>=0;--i)
    if(fa[i][x]!=fa[i][y])
      x=fa[i][x],y=fa[i][y];
  return fa[0][x];
}

inline int jump(int x,int goal){
  for(int i=15;i>=0;--i)
    if(dep[fa[i][x]]>dep[goal])
      x=fa[i][x];
  return x;
}

/*
  把答案(盘子)二分。
  把左边的矩形加进去。
  然后check,calc一下盘子个数,和k比较一下,划分一下。
  递归处理。
*/

inline void solve(int optl,int optr,int l,int r){
  if(optl>optr || l>r)return;++tim;
  if(optl==optr){
    for(int i=l;i<=r;++i)
      Ans[fruit[i].id]=plate[optl].val;
    return;
  }
  int mid=(optl+optr)>>1,tot1=0,tot2=0,k=l,tmp=0,cnt1=1,cnt2=l;
  for(int i=optl;i<=mid;++i){
    Line[++tmp]=(Data){plate[i].xl,plate[i].yl,plate[i].yr,1};
    Line[++tmp]=(Data){plate[i].xr+1,plate[i].yl,plate[i].yr,-1};
  }
  sort(Line+1,Line+tmp+1);
  while(cnt1<=tmp && cnt2<=r){
    if(Line[cnt1].x<=fruit[cnt2].x){
      int xl=Line[cnt1].l,xr=Line[cnt1].r,val=Line[cnt1].val;
      T.update(xl,xr,val);cnt1++;
    }
    else{
      int sum=T.query(fruit[cnt2].y);
      if(sum>=fruit[cnt2].k)que1[++tot1]=fruit[cnt2++];
      else fruit[cnt2].k-=sum,que2[++tot2]=fruit[cnt2++];
    }
  }
  while(cnt2<=r){
    int sum=T.query(fruit[cnt2].y);
    if(sum>=fruit[cnt2].k)que1[++tot1]=fruit[cnt2++];
    else fruit[cnt2].k-=sum,que2[++tot2]=fruit[cnt2++];
  }
  for(int i=1;i<=tot1;++i)fruit[k++]=que1[i];
  for(int i=1;i<=tot2;++i)fruit[k++]=que2[i];
  solve(optl,mid,l,l+tot1-1);
  solve(mid+1,optr,l+tot1,r);
}

int main()
{
  freopen("fruit_hnoi2015.in","r",stdin);
  freopen("fruit_hnoi2015.out","w",stdout);
  n=gi();P=gi();Q=gi();
  for(int i=1;i<n;++i){
    int u=gi(),v=gi();
    link(u,v);link(v,u);
  }
  dfs1(1,1);
  for(int i=1;i<=P;++i){
    int a=gi(),b=gi(),c=gi(),u=lca(a,b);
    if(dfn[a]>dfn[b])swap(a,b);
    if(u!=a)plate[++cnt]=(Plate){dfn[a],last[a],dfn[b],last[b],c};
    else{
      int v=jump(b,a);
      if(dfn[v]>1)plate[++cnt]=(Plate){1,dfn[v]-1,dfn[b],last[b],c};
      if(last[v]<n)plate[++cnt]=(Plate){dfn[b],last[b],last[v]+1,n,c};
    }
  }
  for(int i=1;i<=Q;++i){
    int a=gi(),b=gi(),k=gi();
    if(dfn[a]>dfn[b])swap(a,b);
    fruit[i]=(Fruit){dfn[a],dfn[b],k,i};
  }
  sort(plate+1,plate+cnt+1);
  sort(fruit+1,fruit+Q+1);
  solve(1,cnt,1,Q);
  for(int i=1;i<=Q;++i)printf("%d\n",Ans[i]);
  return 0;
}

  

 

相关文章