程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> SPOJ 10628(COT-樹上第k大-函數式線段樹)

SPOJ 10628(COT-樹上第k大-函數式線段樹)

編輯:C++入門知識

SPOJ Problem Set (classical)
10628. Count on a tree
Problem code: COT

 

You are given a tree with N nodes.The tree nodes are numbered from 1 to N.Each node has an integer weight.

We will ask you to perform the following operation:

u v k : ask for the kth minimum weight on the path from node u to node v
 

Input
In the first line there are two integers N and M.(N,M<=100000)

In the second line there are N integers.The ith integer denotes the weight of the ith node.

In the next N-1 lines,each line contains two integers u v,which describes an edge (u,v).

In the next M lines,each line contains three integers u v k,which means an operation asking for the kth minimum weight on the path from node u to node v.

Output
For each operation,print its result.

Example
Input:
8 58 5
105 2 9 3 8 5 7 7
1 2       
1 3
1 4
3 5
3 6
3 7
4 8
2 5 1
2 5 2
2 5 3
2 5 4
7 8 2 Output:
2
8
9
105
7

我們在樹上每個結點塞一個函數式線段樹。
表示從這個節點到根的鏈所代表的權值線段樹

則(u-v)=(u)+(v)-(lca(u,v))-(fa(lca(u,v)))

 

 

[cpp]
#include<cstdio>  
#include<cstdlib>  
#include<cstring>  
#include<iostream>  
#include<algorithm>  
#include<functional>  
#include<cmath>  
#include<cctype>  
#include<map>  
using namespace std; 
#define For(i,n) for(int i=1;i<=n;i++)  
#define Rep(i,n) for(int i=0;i<n;i++)  
#define Fork(i,k,n) for(int i=k;i<=n;i++)  
#define ForD(i,n) for(int i=n;i;i--)  
#define Forp(x) for(int p=pre[x];p;p=next[p])  
#define RepD(i,n) for(int i=n;i>=0;i--)  
#define MEM(a) memset(a,0,sizeof(a))  
#define MEMI(a) memset(a,127,sizeof(a))  
#define MEMi(a) memset(a,128,sizeof(a))  
#define MAXN (100000+10)  
#define MAXM (200000+10)  
#define Li (18)  
int n,m,w[MAXN]; 
int edge[MAXM],next[MAXM]={0},pre[MAXN]={0},size=0; 
void addedge(int u,int v) 

    edge[++size]=v; 
    next[size]=pre[u]; 
    pre[u]=size; 

void addedge2(int u,int v){addedge(u,v),addedge(v,u);} 
struct node 

    int ch[2],c; 
    node(){ch[0]=ch[1]=c=0;} 
}q[MAXN*Li]; 
int root[MAXN],tail=0; 
void ins(int &x,int p,int l,int r,int c) 

    x=++tail; 
    if (p) q[x]=q[p]; 
    q[x].c++; 
    if (l==r) return; 
    int m=(l+r)>>1; 
    if (c<=m) ins(q[x].ch[0],q[x].ch[0],l,m,c); 
    else ins(q[x].ch[1],q[x].ch[1],m+1,r,c);     

 
map<int ,int> h; 
int a2[MAXN],a2_size; 
 
int d[MAXN],father[MAXN][Li]={0}; 
int q2[MAXN]; 
void bfs() 

    int head=1,tail=1;q2[1]=1;d[1]=1;ins(root[1],root[1],1,a2_size,w[1]); 
    while (head<=tail) 
    { 
        int x=q2[head++]; 
        For(i,Li-1)  
        { 
            father[x][i]=father[father[x][i-1]][i-1]; 
            if (!father[x][i]) break; 
        } 
        Forp(x) 
        { 
            int &v=edge[p]; 
            if (d[v]) continue; 
            d[v]=d[x]+1; 
            father[v][0]=x; 
            q2[++tail]=v; 
            ins(root[v],root[x],1,a2_size,w[v]); 
        } 
    } 

int bin[MAXN]; 
int lca(int u,int v) 

    if (d[u]<d[v]) swap(u,v); 
    int t=d[u]-d[v]; 
    Rep(i,Li) 
        if (bin[i]&t) u=father[u][i]; 
    int i=Li-1; 
    while (u^v) 
    { 
        while (i&&father[u][i]==father[v][i]) i--; 
        u=father[u][i],v=father[v][i]; 
    } 
    return u; 

int ans[MAXN],ans_siz=0,ans_end=0; 
int getsum() 

    int tot=0; 
    For(i,ans_end) tot+=q[q[ans[i]].ch[0]].c; 
    Fork(i,ans_end+1,ans_siz) tot-=q[q[ans[i]].ch[0]].c; 
    return tot; 

void turn(bool c) 

    For(i,ans_siz) ans[i]=q[ans[i]].ch[c]; 

int main() 

//  freopen("spoj10628_COT.in","r",stdin);  
//  freopen(".out","w",stdout);  
     
    bin[0]=1; 
    For(i,Li-1) bin[i]=bin[i-1]<<1; 
         
    scanf("%d%d",&n,&m); 
    For(i,n) scanf("%d",&w[i]),a2[i]=w[i]; 
    sort(a2+1,a2+1+n); 
    int size=unique(a2+1,a2+1+n)-(a2+1);a2_size=size; 
    For(i,size) h[a2[i]]=i; 
    For(i,n) w[i]=h[w[i]]; 
    For(i,n-1)  
    { 
        int u,v; 
        scanf("%d%d",&u,&v); 
        addedge2(u,v); 
    } 
    bfs(); 
    For(i,m) 
    { 
        int u,v,k; 
        scanf("%d%d%d",&u,&v,&k); 
        int f=lca(u,v); 
        ans[1]=root[u],ans[2]=root[v],ans[3]=root[f],ans[4]=root[father[f][0]]; 
        ans_siz=4,ans_end=2; 
        int l=1,r=size; 
        while (l<r) 
        { 
            int m=l+r>>1,s; 
            if (k<=(s=getsum())) r=m,turn(0);else l=m+1,k-=s,turn(1);  
        }        
        printf("%d\n",a2[l]); 
                 
    } 
     
     
    return 0; 

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
#include<cmath>
#include<cctype>
#include<map>
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)
#define Rep(i,n) for(int i=0;i<n;i++)
#define Fork(i,k,n) for(int i=k;i<=n;i++)
#define ForD(i,n) for(int i=n;i;i--)
#define Forp(x) for(int p=pre[x];p;p=next[p])
#define RepD(i,n) for(int i=n;i>=0;i--)
#define MEM(a) memset(a,0,sizeof(a))
#define MEMI(a) memset(a,127,sizeof(a))
#define MEMi(a) memset(a,128,sizeof(a))
#define MAXN (100000+10)
#define MAXM (200000+10)
#define Li (18)
int n,m,w[MAXN];
int edge[MAXM],next[MAXM]={0},pre[MAXN]={0},size=0;
void addedge(int u,int v)
{
 edge[++size]=v;
 next[size]=pre[u];
 pre[u]=size;
}
void addedge2(int u,int v){addedge(u,v),addedge(v,u);}
struct node
{
 int ch[2],c;
 node(){ch[0]=ch[1]=c=0;}
}q[MAXN*Li];
int root[MAXN],tail=0;
void ins(int &x,int p,int l,int r,int c)
{
 x=++tail;
 if (p) q[x]=q[p];
 q[x].c++;
 if (l==r) return;
 int m=(l+r)>>1;
 if (c<=m) ins(q[x].ch[0],q[x].ch[0],l,m,c);
 else ins(q[x].ch[1],q[x].ch[1],m+1,r,c); 
}

map<int ,int> h;
int a2[MAXN],a2_size;

int d[MAXN],father[MAXN][Li]={0};
int q2[MAXN];
void bfs()
{
 int head=1,tail=1;q2[1]=1;d[1]=1;ins(root[1],root[1],1,a2_size,w[1]);
 while (head<=tail)
 {
  int x=q2[head++];
  For(i,Li-1)
  {
   father[x][i]=father[father[x][i-1]][i-1];
   if (!father[x][i]) break;
  }
  Forp(x)
  {
   int &v=edge[p];
   if (d[v]) continue;
   d[v]=d[x]+1;
   father[v][0]=x;
   q2[++tail]=v;
   ins(root[v],root[x],1,a2_size,w[v]);
  }
 }
}
int bin[MAXN];
int lca(int u,int v)
{
 if (d[u]<d[v]) swap(u,v);
 int t=d[u]-d[v];
 Rep(i,Li)
  if (bin[i]&t) u=father[u][i];
 int i=Li-1;
 while (u^v)
 {
  while (i&&father[u][i]==father[v][i]) i--;
  u=father[u][i],v=father[v][i];
 }
 return u;
}
int ans[MAXN],ans_siz=0,ans_end=0;
int getsum()
{
 int tot=0;
 For(i,ans_end) tot+=q[q[ans[i]].ch[0]].c;
 Fork(i,ans_end+1,ans_siz) tot-=q[q[ans[i]].ch[0]].c;
 return tot;
}
void turn(bool c)
{
 For(i,ans_siz) ans[i]=q[ans[i]].ch[c];
}
int main()
{
// freopen("spoj10628_COT.in","r",stdin);
// freopen(".out","w",stdout);
 
 bin[0]=1;
 For(i,Li-1) bin[i]=bin[i-1]<<1;
  
 scanf("%d%d",&n,&m);
 For(i,n) scanf("%d",&w[i]),a2[i]=w[i];
 sort(a2+1,a2+1+n);
 int size=unique(a2+1,a2+1+n)-(a2+1);a2_size=size;
 For(i,size) h[a2[i]]=i;
 For(i,n) w[i]=h[w[i]];
 For(i,n-1)
 {
  int u,v;
  scanf("%d%d",&u,&v);
  addedge2(u,v);
 }
 bfs();
 For(i,m)
 {
  int u,v,k;
  scanf("%d%d%d",&u,&v,&k);
  int f=lca(u,v);
  ans[1]=root[u],ans[2]=root[v],ans[3]=root[f],ans[4]=root[father[f][0]];
  ans_siz=4,ans_end=2;
  int l=1,r=size;
  while (l<r)
  {
   int m=l+r>>1,s;
   if (k<=(s=getsum())) r=m,turn(0);else l=m+1,k-=s,turn(1);
  }  
  printf("%d\n",a2[l]);
    
 }
 
 
 return 0;
}

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved