HDU 4916 树形dp

阅读量：7103 次

发布时间：2019-06-28

本文共 3607 字，大约阅读时间需要 12 分钟。

Count on the path

Time Limit: 5000/2500 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 92 Accepted Submission(s): 10

Problem Description

bobo has a tree, whose vertices are conveniently labeled by 1,2,…,n.

Let f(a,b) be the minimum of vertices

not on the path between vertices a and b.

There are q queries (u

_i,v

_i) for the value of f(u

_i,v

_i). Help bobo answer them.

Input

The input consists of several tests. For each tests:

The first line contains 2 integers n,q (4≤n≤10

⁶,1≤q≤10

⁶). Each of the following (n - 1) lines contain 2 integers a

_i,b

_i denoting an edge between vertices a

_i and b

_i (1≤a

_i,b

_i≤n). Each of the following q lines contains 2 integer u′

_i,v′

_i (1≤u

_i,v

_i≤n).

The queries are encrypted in the following manner.

₁=u′

₁,v

₁=v′

₁.

For i≥2, u

_i=u′

_i⊕f(u

_{i - 1},v

_{i - 1}),v

_i=v′

_i⊕f(u

_i-1,v

_i-1).

Note ⊕ denotes bitwise exclusive-or.

It is guaranteed that f(a,b) is defined for all a,b.

The task contains huge inputs. `scanf` in g++ is considered too slow to get accepted. You may (1) submit the solution in c++; or (2) use hand-written input utilities.

Output

For each tests:

For each queries, a single number denotes the value.

Sample Input

       4 1 1 2 1 3 1 4 2 3 5 2 1 2 1 3 2 4 2 5 1 2 7 6 

Sample Output

       4 3 1 

Author

Xiaoxu Guo (ftiasch)

给定一棵树，求不经过路径的最小标号。

把1作为根，然后增加不经过1，那么答案直接为1，否则就是预处理，

数据规模非常大，所以仅仅能用bfs，而且须要加读写外挂，具体过程代码具体解释。

代码：

/* ***********************************************Author :rabbitCreated Time :2014/8/6 10:44:17File Name :5.cpp************************************************ */#pragma comment(linker, "/STACK:102400000,102400000")#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  #include 
                  using namespace std;#define INF 0x3f3f3f3f#define eps 1e-8#define pi acos(-1.0)typedef long long ll;int fun(){ char ch;int flag=1,a=0; while(ch=getchar())if((ch>='0'&&ch<='9')||ch=='-')break; if(ch=='-')flag=-1;else a=ch-'0'; while(ch=getchar()){ if(ch>='0'&&ch<='9')a=10*a+ch-'0'; else break; } return flag*a;}const int maxn=1001000;int head[maxn],tol;int subtree[maxn];//子树最小标号int belong[maxn];//所在的与根节点1相连的子树最小标号。int child[maxn][4];//儿子子树前4小。int que[maxn];//广搜队列。int path[maxn];//path[u]代表u所在的在根节点1的儿子的子树中从根节点到u路径以外的最小标号。int fa[maxn];//父亲标号。int dep[maxn];//深度数组struct Edge{ int next,to;}edge[2*maxn];void addedge(int u,int v){ edge[tol].to=v; edge[tol].next=head[u]; head[u]=tol++;}int main(){ //freopen("data.in","r",stdin); //freopen("data.out","w",stdout); int n,m; while(~scanf("%d%d",&n,&m)){ memset(head,-1,sizeof(head));tol=0; for(int i=1;i
                   
                    =0;i--){ int u=que[i]; subtree[u]=min(u,child[u][0]); int p=fa[u]; if(p==-1)continue; child[p][3]=subtree[u]; sort(child[p],child[p]+4); } front=0,rear=0; path[1]=INF; belong[1]=-1; for(int i=head[1];i!=-1;i=edge[i].next){ int u=edge[i].to; path[u]=INF; belong[u]=subtree[u]; que[rear++]=u; } while(front!=rear){ int u=que[front++]; for(int i=head[u];i!=-1;i=edge[i].next){ int v=edge[i].to; if(v==fa[u])continue; path[v]=min(path[u],child[u][subtree[v]==child[u][0]]); belong[v]=belong[u]; que[rear++]=v; } path[u]=min(path[u],child[u][0]);//u的儿子子树的最小标号。 } int last=0; while(m--){ int u,v; u=fun();v=fun(); u^=last;v^=last; if(u>v)swap(u,v); if(u!=1&&belong[u]==belong[v])last=1;//假设不经过1，而且属于同一个根节点的儿子的子树，答案直接为1 else{ int i=0; while(child[1][i]==belong[u]||child[1][i]==belong[v])i++;//把包括u，v的儿子子树跳过。 last=u==1?path[v]:min(path[u],path[v]);//路径分为两段，取最小值。 last=min(last,child[1][i]);//出去u，v所在的子树以外的最小值。 } printf("%d\n",last); } } return 0;}