首页 > 代码库 > Count on the path

Count on the path

2024-08-15 21:19:33   223人阅读

Count on the path

Time Limit: 5000/2500 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others)

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 (ui,vi) for the value of f(ui,vi). Help bobo answer them.
 

 

Input
The input consists of several tests. For each tests:

The first line contains 2 integers n,q (4≤n≤106,1≤q≤106). Each of the following (n - 1) lines contain 2 integers ai,bi denoting an edge between vertices ai and bi (1≤ai,bi≤n). Each of the following q lines contains 2 integer u′i,v′i (1≤ui,vi≤n).

The queries are encrypted in the following manner.

u1=u′1,v1=v′1.
For i≥2, ui=u′i⊕f(ui - 1,vi - 1),vi=v′i⊕f(ui-1,vi-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 11 21 31 42 35 21 21 32 42 51 27 6
 

 

Sample Output
431
分析：参考http://www.lai18.com/content/8107004.html；
　　　学到的东西很多，比如求子树的第二小，在当前根下却不在其中一个儿子的子树的最小值；
　　　bel[i]表示i在1的哪个儿子下，fa[i]表示i的父亲，son[i]表示i的所有子树里面最小的节点，sec_son[i]对所有i的儿子j的son[j]排序后取第二小的；
　　　dp[i]表示不是i，却是i的父亲的儿子j下的最小son[j]，dp1[i]表示从1走到i所有分支子树下的最小节点；
代码：
#include <iostream>#include <cstdio>#include <cstdlib>#include <cmath>#include <algorithm>#include <climits>#include <cstring>#include <string>#include <set>#include <map>#include <queue>#include <stack>#include <vector>#include <list>#define rep(i,m,n) for(i=m;i<=n;i++)#define rsp(it,s) for(set<int>::iterator it=s.begin();it!=s.end();it++)#define mod 1000000007#define inf 0x3f3f3f3f#define vi vector<int>#define pb push_back#define mp make_pair#define fi first#define se second#define ll long long#define pi acos(-1.0)#define pii pair<int,int>#define Lson L, mid, ls[rt]#define Rson mid+1, R, rs[rt]const int maxn=1e6+10;using namespace std;ll gcd(ll p,ll q){return q==0?p:gcd(q,p%q);}ll qpow(ll p,ll q){ll f=1;while(q){if(q&1)f=f*p;p=p*p;q>>=1;}return f;}inline ll read(){    ll x=0;int f=1;char ch=getchar();    while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}    while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}    return x*f;}int n,m,k,t,q,tot,h[maxn],bel[maxn],fa[maxn],son[maxn],sec_son[maxn],dp[maxn],dp1[maxn],ans;struct node{    int to,nxt;}e[maxn<<1];void add(int x,int y){    tot++;    e[tot].to=y;    e[tot].nxt=h[x];    h[x]=tot;}void dfs(int now,int pre){    son[now]=sec_son[now]=inf;    for(int i=h[now];i;i=e[i].nxt)    {        int to=e[i].to;        if(to!=pre)        {            fa[to]=now;            if(now!=1)bel[to]=bel[now];            dfs(to,now);            if(son[now]>min(son[to],to))            {                sec_son[now]=son[now];                son[now]=min(son[to],to);            }        }    }}void dfs1(int now,int pre){    if(now!=1)dp1[now]=min(dp1[fa[now]],dp[now]);    else dp1[now]=inf;    for(int i=h[now];i;i=e[i].nxt)    {        int to=e[i].to;        if(to!=pre)        {            dfs1(to,now);        }    }}void solve(int x,int y){    int now_ans=inf;    for(int i=h[1];i;i=e[i].nxt)    {        int to=e[i].to;        if(to!=bel[x]&&to!=bel[y])now_ans=min(min(now_ans,son[to]),to);    }    if(x!=1)now_ans=min(now_ans,son[x]);    if(y!=1)now_ans=min(now_ans,son[y]);    now_ans=min(now_ans,dp1[x]);    now_ans=min(now_ans,dp1[y]);    ans=now_ans;}int main(){    int i,j;    while(~scanf("%d%d",&n,&q))    {        ans=0;        tot=0;        memset(h,0,sizeof(h));        rep(i,1,n)bel[i]=i;        rep(i,1,n-1)        {            int a,b;            scanf("%d%d",&a,&b);            add(a,b);            add(b,a);        }        dfs(1,0);        rep(i,2,n)        {            if(fa[i]==1)            {                dp[i]=inf;                continue;            }            if(min(son[i],i)!=son[fa[i]])dp[i]=son[fa[i]];            else dp[i]=sec_son[fa[i]];        }        dfs1(1,0);        while(q--)        {            int a,b;            scanf("%d%d",&a,&b);            a^=ans,b^=ans;            if(bel[a]==bel[b])ans=1;            else solve(a,b);            printf("%d\n",ans);        }    }    //system("Pause");    return 0;}

Count on the path


联系
我们