专题训练之LCA

推荐几个博客：https://www.cnblogs.com/JVxie/p/4854719.html Tarjan离线算法的基本思路及其算法实现

https://blog.csdn.net/shahdza/article/details/7779356 LCA题集

http://www.cnblogs.com/zhouzhendong/p/7256007.html LCA的三种算法介绍

模板（题）：

1.（POJ1470）http://poj.org/problem?id=1470

Tarjan离线算法

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<iostream>

 using namespace std;

 const int maxn=;

 const int maxm=;

 struct Edge{

     int to,nxt;

 }edge[maxn*];

 struct Query{

     int q,nxt;

     int index;

 }query[maxm*];

 int f[maxn],anc[maxn];

 bool vis[maxn];

 int head[maxn],tot;

 int ans[maxm],h[maxm],tt,Q;

 bool flag[maxn];

 int num[maxn];

 int find(int x)

 {

     if ( f[x]==- ) return x;

     return f[x]=find(f[x]);

 }

 void merge(int x,int y)

 {

     int fx=find(x);

     int fy=find(y);

     if ( fx!=fy ) f[fx]=fy;

 }

 void addedge(int u,int v)

 {

     edge[tot].to=v;

     edge[tot].nxt=head[u];

     head[u]=tot++;

 }

 void addquery(int u,int v,int index)

 {

     query[tt].q=v;

     query[tt].nxt=h[u];

     query[tt].index=index;

     h[u]=tt++;

     query[tt].q=u;

     query[tt].nxt=h[v];

     query[tt].index=index;

     h[v]=tt++;

 }

 void init()

 {

     tot=;

     memset(head,-,sizeof(head));

     tt=;

     memset(h,-,sizeof(h));

     memset(vis,false,sizeof(vis));

     memset(f,-,sizeof(f));

     memset(anc,,sizeof(anc));

 }

 void LCA(int u)

 {

     anc[u]=u;

     vis[u]=true;

     for ( int i=head[u];i!=-;i=edge[i].nxt )

     {

         int v=edge[i].to;

         if ( vis[v] ) continue;

         LCA(v);

         merge(u,v);

         anc[find(u)]=u;

     }

     for ( int i=h[u];i!=-;i=query[i].nxt )

     {

         int v=query[i].q;

         if ( vis[v] ) ans[query[i].index]=anc[find(v)];

     }

 }

 int main()

 {

     int n,u,v,k;

     while ( scanf("%d",&n)!=EOF )

     {

         init();

         memset(flag,false,sizeof(flag));

         for ( int i=;i<=n;i++ )

         {

             scanf("%d:(%d)",&u,&k);

             while ( k-- )

             {

                 scanf("%d",&v);

                 flag[v]=true;

                 addedge(u,v);

                 addedge(v,u);

             }

         }

         scanf("%d",&Q);

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

         {

             char ch;

             cin>>ch;

             scanf("%d %d)",&u,&v);

             addquery(u,v,i);

         }

         int root;

         for ( int i=;i<=n;i++ )

         {

             if ( !flag[i] )

             {

                 root=i;

                 break;

             }

         }

         LCA(root);

         memset(num,,sizeof(num));

         for ( int i=;i<Q;i++ ) num[ans[i]]++;

         for ( int i=;i<=n;i++ )

         {

             if ( num[i]> ) printf("%d:%d\n",i,num[i]);

         }

     }

     return ;

 }

POJ1470

2.（POJ1330）http://poj.org/problem?id=1330

倍增法在线算法

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<queue>

 using namespace std;

 const int maxn=1e4+;

 const int DEG=;

 struct Edge{

     int to,nxt;

 }edge[maxn*];

 int head[maxn],tot;

 int fa[maxn][DEG]; //fa[i][j]表示节点i的第2^j个祖先

 int deg[maxn];

 bool flag[maxn];

 void addedge(int u,int v)

 {

     edge[tot].to=v;

     edge[tot].nxt=head[u];

     head[u]=tot++;

 }

 void init()

 {

     tot=;

     memset(head,-,sizeof(head));

 }

 void BFS(int root)

 {

     queue<int>que;

     deg[root]=;

     fa[root][]=root;

     que.push(root);

     while ( !que.empty() )

     {

         int tmp=que.front();

         que.pop();

         for ( int i=;i<DEG;i++ ) fa[tmp][i]=fa[fa[tmp][i-]][i-];

         for ( int i=head[tmp];i!=-;i=edge[i].nxt )

         {

             int v=edge[i].to;

             if ( v==fa[tmp][] ) continue;

             deg[v]=deg[tmp]+;

             fa[v][]=tmp;

             que.push(v);

         }

     }

 }

 int LCA(int u,int v)

 {

     if ( deg[u]>deg[v] ) swap(u,v);

     int hu=deg[u],hv=deg[v];

     int tu=u,tv=v;

     for ( int det=hv-hu,i=;det;det>>=,i++ )

     {

         if ( det& ) tv=fa[tv][i];

     }

     if ( tu==tv ) return tu;

     for ( int i=DEG-;i>=;i-- )

     {

         if ( fa[tu][i]==fa[tv][i] ) continue;

         tu=fa[tu][i];

         tv=fa[tv][i];

     }

     return fa[tu][];

 }

 int main()

 {

     int T,n,u,v;

     scanf("%d",&T);

     while ( T-- )

     {

         scanf("%d",&n);

         init();

         memset(flag,false,sizeof(flag));

         for ( int i=;i<n;i++ )

         {

             scanf("%d%d",&u,&v);

             addedge(u,v);

             addedge(v,u);

             flag[v]=true;

         }

         int root;

         for ( int i=;i<=n;i++ )

         {

             if ( !flag[i] )

             {

                 root=i;

                 break;

             }

         }

         BFS(root);

         scanf("%d%d",&u,&v);

         printf("%d\n",LCA(u,v));

     }

     return ;

 }

POJ1330

ST+DFS在线算法

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 const int maxn=;

 int rmq[maxn*]; //即欧拉序列对应的深度序列

 struct ST

 {

     int mm[*maxn];

     int dp[*maxn][]; //最小值对应的下标

     void init(int n)

     {

         mm[]=-;

         for ( int i=;i<=n;i++ )

         {

             mm[i]=((i&(i-))==)?mm[i-]+:mm[i-];

             dp[i][]=i;

         }

         for ( int j=;j<=mm[n];j++ )

         {

             for ( int i=;i+(<<j)-<=n;i++ )

             {

                 if ( rmq[dp[i][j-]]<rmq[dp[i+(<<(j-))][j-]] ) dp[i][j]=dp[i][j-];

                 else dp[i][j]=dp[i+(<<(j-))][j-];

             }

         }

     }

     int query(int a,int b) //查询[a,b] 之间最小值的下标

     {

         if ( a>b ) swap(a,b);

         int k=mm[b-a+];

         if ( rmq[dp[a][k]]<=rmq[dp[b-(<<k)+][k]] ) return dp[a][k];

         else return dp[b-(<<k)][k];

     }

 };

 struct Edge{

     int to,nxt;

 }edge[maxn*];

 int tot,head[maxn];

 int F[maxn],P[maxn],cnt; //F为欧拉序（即DFS遍历的顺序）,长度为2*n-1，从1开始;P为所有点第一次在F中出现的位置

 ST st;

 void init()

 {

     tot=;

     memset(head,-,sizeof(head));

 }

 void addedge(int u,int v) //加边，无向边需要加两次

 {

     edge[tot].to=v;

     edge[tot].nxt=head[u];

     head[u]=tot++;

 }

 void dfs(int u,int pre,int dep)

 {

     F[++cnt]=u;

     rmq[cnt]=dep;

     P[u]=cnt;

     for ( int i=head[u];i!=-;i=edge[i].nxt )

     {

         int v=edge[i].to;

         if ( v==pre ) continue;

         dfs(v,u,dep+);

         F[++cnt]=u;

         rmq[cnt]=dep;

     }

 }

 void LCA_init(int root,int num) //查询LCA前的初始化

 {

     cnt=;

     dfs(root,root,);

     st.init(*num-);

 }

 int query(int u,int v) //查询LCA(u,v)的编号

 {

     return F[st.query(P[u],P[v])];

 }

 bool flag[maxn];

 int main()

 {

     int T,N,u,v;

     scanf("%d",&T);

     while ( T-- )

     {

         scanf("%d",&N);

         init();

         memset(flag,false,sizeof(flag));

         for ( int i=;i<N;i++ )

         {

             scanf("%d%d",&u,&v);

             addedge(u,v);

             addedge(v,u);

             flag[v]=true;

         }

         int root;

         for ( int i=;i<=N;i++ )

         {

             if ( !flag[i] )

             {

                 root=i;

                 break;

             }

         }

         LCA_init(root,N);

         scanf("%d%d",&u,&v);

         printf("%d\n",query(u,v));

     }

     return ;

 }

POJ1330

练习题：

1.（HDOJ2586）http://acm.hdu.edu.cn/showproblem.php?pid=2586

题意：求给定两点之间的距离

分析：如果t是u，v的最近公共祖先，那么d[u,v]=d[u,root]+d[v,root]-2*d[t,root]，所以我们只需要在倍增算法的BFS中每次更新深度时同时把距离一起更新掉即可

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<queue>

 using namespace std;

 const int maxn=4e4+;

 const int DEG=;

 const int inf=1e9;

 struct Edge{

     int to,nxt,w;

 }edge[maxn*];

 int head[maxn],tot;

 int fa[maxn][DEG]; //fa[i][j]表示节点i的第2^j个祖先

 int deg[maxn];

 bool flag[maxn];

 int n,d[maxn];

 void addedge(int u,int v,int w)

 {

     edge[tot].to=v;

     edge[tot].nxt=head[u];

     edge[tot].w=w;

     head[u]=tot++;

 }

 void init()

 {

     tot=;

     memset(head,-,sizeof(head));

 }

 void BFS(int root)

 {

     queue<int>que;

     for ( int i=;i<=n;i++ ) d[i]=inf;

     d[root]=;

     deg[root]=;

     fa[root][]=root;

     que.push(root);

     while ( !que.empty() )

     {

         int tmp=que.front();

         que.pop();

         for ( int i=;i<DEG;i++ ) fa[tmp][i]=fa[fa[tmp][i-]][i-];

         for ( int i=head[tmp];i!=-;i=edge[i].nxt )

         {

             int v=edge[i].to;

             int w=edge[i].w;

             if ( v==fa[tmp][] ) continue;

             deg[v]=deg[tmp]+;

             d[v]=min(d[v],d[tmp]+w);

             fa[v][]=tmp;

             que.push(v);

         }

     }

 }

 int LCA(int u,int v)

 {

     if ( deg[u]>deg[v] ) swap(u,v);

     int hu=deg[u],hv=deg[v];

     int tu=u,tv=v;

     for ( int det=hv-hu,i=;det;det>>=,i++ )

     {

         if ( det& ) tv=fa[tv][i];

     }

     if ( tu==tv ) return tu;

     for ( int i=DEG-;i>=;i-- )

     {

         if ( fa[tu][i]==fa[tv][i] ) continue;

         tu=fa[tu][i];

         tv=fa[tv][i];

     }

     return fa[tu][];

 }

 int main()

 {

     int T,u,v,w,m,x,ans;

     scanf("%d",&T);

     while ( T-- )

     {

         scanf("%d%d",&n,&m);

         init();

         memset(flag,false,sizeof(flag));

         for ( int i=;i<n;i++ )

         {

             scanf("%d%d%d",&u,&v,&w);

             addedge(u,v,w);

             addedge(v,u,w);

             flag[v]=true;

         }

         int root;

         for ( int i=;i<=n;i++ )

         {

             if ( !flag[i] )

             {

                 root=i;

                 break;

             }

         }

         BFS(root);

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

         {

             scanf("%d%d",&u,&v);

             x=LCA(u,v);

             ans=d[u]+d[v]-*d[x];

             printf("%d\n",ans);

         }

     }

     return ;

 }

HDOJ2586

2.（HDOJ2874）http://acm.hdu.edu.cn/showproblem.php?pid=2874

题意：给出一个森林，求给定两点之间的距离

分析：Tarjan离线算法，有多个根节点，每次询问时判断两个点是否处于同一个树上。LCA传入参数时需要传入当前的点，距离根节点的距离，根节点的编号。但是此题卡内存

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<iostream>

 using namespace std;

 const int maxn=1e4+;

 const int maxm=1e6+;

 struct Edge{

     int to,nxt,w;

 }edge[maxn*];

 struct Query{

     int q,nxt;

     int index;

 }query[maxm*];

 int f[maxn],anc[maxn];

 int head[maxn],tot;

 int ans[maxm],h[maxm],tt,Q,belong[maxn];

 int n,d[maxn];

 int find(int x)

 {

     if ( f[x]==- ) return x;

     return f[x]=find(f[x]);

 }

 void merge(int x,int y)

 {

     int fx=find(x);

     int fy=find(y);

     if ( fx!=fy ) f[fx]=fy;

 }

 void addedge(int u,int v,int w)

 {

     edge[tot].to=v;

     edge[tot].nxt=head[u];

     edge[tot].w=w;

     head[u]=tot++;

 }

 void addquery(int u,int v,int index)

 {

     query[tt].q=v;

     query[tt].nxt=h[u];

     query[tt].index=index;

     h[u]=tt++;

     query[tt].q=u;

     query[tt].nxt=h[v];

     query[tt].index=index;

     h[v]=tt++;

 }

 void init()

 {

     tot=;

     memset(head,-,sizeof(head));

     tt=;

     memset(h,-,sizeof(h));

     memset(f,-,sizeof(f));

     memset(anc,,sizeof(anc));

 }

 void LCA(int u,int deep,int root)

 {

     anc[u]=u;

     belong[u]=root;

     d[u]=deep;

     for ( int i=head[u];i!=-;i=edge[i].nxt )

     {

         int v=edge[i].to;

         int w=edge[i].w;

         if ( belong[v]!=- ) continue;

         LCA(v,deep+w,root);

         merge(u,v);

         anc[find(u)]=u;

     }

     for ( int i=h[u];i!=-;i=query[i].nxt )

     {

         int v=query[i].q;

         if ( belong[v]==root )

         {

             int sum=d[u]+d[v]-*d[anc[find(v)]];

             ans[query[i].index]=sum;

         }

     }

 }

 int main()

 {

     int u,v,w,k,m,q,x;

     while ( scanf("%d%d%d",&n,&m,&Q)!=EOF )

     {

         init();

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

         {

             scanf("%d%d%d",&u,&v,&w);

             addedge(u,v,w);

             addedge(v,u,w);

         }

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

         {

             ans[i]=-;

             scanf("%d%d",&u,&v);

             addquery(u,v,i);

         }

         memset(belong,-,sizeof(belong));

         memset(d,-,sizeof(d));

         for ( int i=;i<=n;i++ )

         {

             if ( belong[i]==- ) LCA(i,,i);

         }

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

         {

             if ( ans[i]!=- ) printf("%d\n",ans[i]);

             else printf("Not connected\n");

         }

     }

     return ;

 }

HDOJ2874（MLE）

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<queue>

 #include<vector>

 using namespace std;

 typedef long long LL;

 const int maxm=2e4+;

 const int maxn=1e4+;

 const int maxq=2e6+;

 struct Node{

     int to;

     int w;

     int next;

 }e[maxm];

 int eh[maxn],dis[maxn],pre[maxn],etol,vis[maxn];

 struct Query{

     int to;

     int index;

     int next;

 }qe[maxq];

 int qh[maxn],ans[maxq/],qtol;

 int n,m,c;

 void init()

 {

     etol=qtol=;

     memset(eh,-,sizeof(eh));

     memset(qh,-,sizeof(qh));

 }

 void add1(int u,int v,int w)

 {

     e[etol].to=v;

     e[etol].w=w;

     e[etol].next=eh[u];

     eh[u]=etol++;

 }

 void add2(int u,int v,int id)

 {

     qe[qtol].index=id;

     qe[qtol].to=v;

     qe[qtol].next=qh[u];

     qh[u]=qtol++;

 }

 int Find(int u)

 {

     if(pre[u]!=u) pre[u]=Find(pre[u]);

     return pre[u];

 }

 void LCA(int u,int deep,int root)

 {

     pre[u]=u;

     dis[u]=deep;

     vis[u]=root;

     for(int i=eh[u];~i;i=e[i].next)

     {

         int v=e[i].to;

         if(vis[v]==-)

         {

             LCA(v,deep+e[i].w,root);

             pre[v]=u;

         }

     }

     for(int i=qh[u];~i;i=qe[i].next)

     {

         int v=qe[i].to;

         if(vis[v]==root)

             ans[qe[i].index]=dis[v]+dis[u]-*dis[Find(v)];

     }

 }

 int main()

 {

     while(~scanf("%d%d%d",&n,&m,&c))

     {

         int u,v,w;

         init();

         while(m--)

         {

             scanf("%d%d%d",&u,&v,&w);

             add1(u,v,w);

             add1(v,u,w);

         }

         for(int i=;i<c;i++)

         {

             scanf("%d%d",&u,&v);

             ans[i]=-;

             add2(u,v,i);

             add2(v,u,i);

         }

         memset(vis,-,sizeof(vis));

         for(int i=;i<=n;i++){

             if(vis[i]==-)

                 LCA(i,,i);

         }

         for(int i=;i<c;i++)

         {

             if(ans[i]==-) puts("Not connected");

             else printf("%d\n",ans[i]);

         }

     }

     return ;

 }

HDOJ2874（参考的AC代码）

3.（HDOJ5044）http://acm.hdu.edu.cn/showproblem.php?pid=5044

题意：给出一颗树，有m个操作，若为add1 u v w表示从u到v经过点的点权都+w，add2 u v w表示从u到v经过点的边权都+w

分析：以下解释摘自：https://blog.csdn.net/hongrock/article/details/39616757

找到U, V的最近公共祖先X。

add[i][0]表示第i个点的权值。

des[i]表示第i个点在计算完之后，应该减少的权值。

add[i][1]表示第i个点跟其父结点之间的边的权值。

对于操作1有：add[u][0]+=w add[v][0]+=w add[X][0]-=w des[X]+=w;

对于操作2有：add[u][1]+=w add[v][1]+=w add[X][1]-=2*w

关于操作的解释：

对于第一种操作，肯定U到X的路径的结点增加K，V到X的路径也增加K。

所以我们可以通过将add[U][0]和add[V][0]的信息不断传递上去，直到X为止。

由于U和V都会传递一个K给X，所以add[X][0]减掉一个K。

处理完X了，K不能再传给其父节点，所以再用des[X]减掉一次。

对于第二种操作，同理，也是不断将信息向上传递。但由于这里是边，不会算两次，所以直接在X的位置减掉两倍K即可。

完成以上后，进行bfs，每次将叶子节点（入度为0的点）不断投入栈中，求出每个点/边的权值

最后注意下N=1的时候，虽然没有边，但是输出边权还是要留个空行给它。

注意：此题卡空间卡时间，要输入输出外挂，还要人工手动加栈，初始化要少等等优化

 #pragma comment(linker, "/STACK:1024000000,1024000000")

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<queue>

 using namespace std;

 typedef long long ll;

 const int maxn=1e5+;

 const int DEG=;

 struct Edge{

     int to,nxt;

 }edge[maxn*];

 int head[maxn],tot;

 int fa[maxn][DEG]; //fa[i][j]表示节点i的第2^j个祖先

 int deg[maxn];

 ll add[maxn][],node[maxn],edg[maxn],des[maxn];

 int du[maxn],tp[maxn];

 bool flag[maxn];

 void addedge(int u,int v)

 {

     edge[tot].to=v;

     edge[tot].nxt=head[u];

     head[u]=tot++;

 }

 void init()

 {

     tot=;

     memset(head,-,sizeof(head));

 }

 void BFS(int root)

 {

     queue<int>que;

     deg[root]=;

     fa[root][]=root;

     que.push(root);

     while ( !que.empty() )

     {

         int tmp=que.front();

         que.pop();

         for ( int i=;i<DEG;i++ ) fa[tmp][i]=fa[fa[tmp][i-]][i-];

         for ( int i=head[tmp];i!=-;i=edge[i].nxt )

         {

             int v=edge[i].to;

             if ( v==fa[tmp][] ) continue;

             tp[v]=i/+;

             du[tmp]++;

             deg[v]=deg[tmp]+;

             fa[v][]=tmp;

             que.push(v);

         }

     }

 }

 int LCA(int u,int v)

 {

     if ( deg[u]>deg[v] ) swap(u,v);

     int hu=deg[u],hv=deg[v];

     int tu=u,tv=v;

     for ( int det=hv-hu,i=;det;det>>=,i++ )

     {

         if ( det& ) tv=fa[tv][i];

     }

     if ( tu==tv ) return tu;

     for ( int i=DEG-;i>=;i-- )

     {

         if ( fa[tu][i]==fa[tv][i] ) continue;

         tu=fa[tu][i];

         tv=fa[tv][i];

     }

     return fa[tu][];

 }

 void bfs(int n)

 {

     queue<int>que;

     for ( int i=;i<=n;i++ )

     {

         if ( !du[i] ) que.push(i);

     }

     while ( !que.empty() )

     {

         int u=que.front();

         que.pop();

         node[u]=add[u][];

         add[u][]-=des[u];

         int v=fa[u][];

         add[v][]+=add[u][];

         add[v][]+=add[u][];

         edg[tp[u]]+=add[u][];

         if ( !(--du[v]) ) que.push(v);

     }

 }

 inline bool scan_d(int &num)

 {

     char in;bool IsN=false;

     in=getchar();

     if(in==EOF) return false;

     while(in!='-'&&(in<''||in>'')) in=getchar();

     if(in=='-'){ IsN=true;num=;}

     else num=in-'';

     while(in=getchar(),in>=''&&in<=''){

             num*=,num+=in-'';

     }

     if(IsN) num=-num;

     return true;

 }

 inline void out(long long x) {

     if(x>) out(x/);

     putchar(x%+'');

 }  

 int main()

 {

     int T,n,u,v,w,q,h,l;

     char op[];

     scan_d(T);

     for ( h=;h<=T;h++ )

     {

         scan_d(n);

         scan_d(q);

         init();

         for ( int i=;i<=n;i++ )

         {

             //flag[i]=false;

             add[i][]=add[i][]=;

             des[i]=du[i]=node[i]=edg[i]=;

         }

         //memset(flag,false,sizeof(flag));

         //memset(add,0,sizeof(add));

         //memset(des,0,sizeof(des));

         //memset(du,0,sizeof(du));

         //memset(node,0,sizeof(node));

         //memset(edg,0,sizeof(edg));

         for ( int i=;i<n;i++ )

         {

             scan_d(u);

             scan_d(v);

             addedge(u,v);

             addedge(v,u);

         }

         int root=;

         /*

         for ( int i=1;i<=n;i++ )

         {

             if ( !flag[i] )

             {

                 root=i;

                 break;

             }

         }

         */

         BFS(root);

         while ( q-- )

         {

             scanf("%s",op);

             scan_d(u);

             scan_d(v);

             scan_d(w);

             l=LCA(u,v);

             if ( op[]=='' )

             {

                 add[u][]+=w;

                 add[v][]+=w;

                 add[l][]-=w;

                 des[l]+=w;

             }

             else

             {

                 add[u][]+=w;

                 add[v][]+=w;

                 add[l][]-=*w;

             }

         }

         bfs(n);

         printf("Case #%d:\n",h);

         for ( int i=;i<=n;i++ )

         {

             out(node[i]);

             if ( i!=n ) printf(" ");

             else printf("\n");

         }

         for ( int i=;i<n;i++ )

         {

             out(edg[i]);

             if ( i!=(n-) ) printf(" ");

             else printf("\n");

         }

         if ( n== ) printf("\n");

     }

     return ;

 }

HDOJ5044（TLE）

4.（HDOJ4547）http://acm.hdu.edu.cn/showproblem.php?pid=4547

分析:从节点a出发，a到任意一个子节点只需要1步，a到任意一个父节点为两个点的距离差。所以询问给出u,v时，先求出l=lca(u,v)，ans=dis[u]-dis[l],如果v于l不是同一个点则ans++（从l一步到达v）

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<queue>

 #include<map>

 #include<string>

 #include<iostream>

 using namespace std;

 const int maxn=1e5+;

 const int DEG=;

 struct Edge{

     int to,nxt,w;

 }edge[maxn*];

 int head[maxn],tot;

 int fa[maxn][DEG]; //fa[i][j]表示节点i的第2^j个祖先

 int deg[maxn];

 bool flag[maxn];

 int dis[maxn];

 map<string,int>mp;

 void addedge(int u,int v,int w)

 {

     edge[tot].to=v;

     edge[tot].nxt=head[u];

     edge[tot].w=w;

     head[u]=tot++;

 }

 void init()

 {

     tot=;

     memset(head,-,sizeof(head));

 }

 void BFS(int root)

 {

     queue<int>que;

     deg[root]=;

     fa[root][]=root;

     que.push(root);

     while ( !que.empty() )

     {

         int tmp=que.front();

         que.pop();

         for ( int i=;i<DEG;i++ ) fa[tmp][i]=fa[fa[tmp][i-]][i-];

         for ( int i=head[tmp];i!=-;i=edge[i].nxt )

         {

             int v=edge[i].to;

             int w=edge[i].w;

             if ( v==fa[tmp][] ) continue;

             dis[v]=dis[tmp]+w;

             deg[v]=deg[tmp]+;

             fa[v][]=tmp;

             que.push(v);

         }

     }

 }

 int LCA(int u,int v)

 {

     if ( deg[u]>deg[v] ) swap(u,v);

     int hu=deg[u],hv=deg[v];

     int tu=u,tv=v;

     for ( int det=hv-hu,i=;det;det>>=,i++ )

     {

         if ( det& ) tv=fa[tv][i];

     }

     if ( tu==tv ) return tu;

     for ( int i=DEG-;i>=;i-- )

     {

         if ( fa[tu][i]==fa[tv][i] ) continue;

         tu=fa[tu][i];

         tv=fa[tv][i];

     }

     return fa[tu][];

 }

 int main()

 {

     int T,n,q,u,v,w,num,l,ans;

     string s1,s2;

     scanf("%d",&T);

     while ( T-- )

     {

         scanf("%d%d",&n,&q);

         mp.clear();

         init();

         num=;

         memset(flag,false,sizeof(flag));

         memset(dis,,sizeof(dis));

         for ( int i=;i<n;i++ )

         {

             cin>>s1>>s2;

             if ( !mp[s1] ) mp[s1]=++num;

             if ( !mp[s2] ) mp[s2]=++num;

             v=mp[s1];

             u=mp[s2];

             addedge(u,v,);

             flag[v]=true;

         }

         int root;

         for ( int i=;i<=n;i++ )

         {

             if ( !flag[i] )

             {

                 root=i;

                 break;

             }

         }

         BFS(root);

         while ( q-- )

         {

             cin>>s1>>s2;

             u=mp[s1];

             v=mp[s2];

             l=LCA(u,v);

             ans=dis[u]-dis[l];

             if ( l!=v ) ans++;

             printf("%d\n",ans);

         }

     }

     return ;

 }

HDOJ4547

5.（HDOJ5274）http://acm.hdu.edu.cn/showproblem.php?pid=5274

题意：有一颗树，有n个点，每个点都有个点权。现在有q个询问，总共有两种操作
0 x y代表把编号为x点的权值变成y

1 x y求出点x到点y的路径上出现点权值为奇数的点，若都为偶数则输出-1。题目保证最多只有一个为奇数的点权值

分析：官方题解：

题目里有一个很神奇的性质：路径上最多只有一个数出现奇数次。

这应该马上想到异或。因为异或两次和没异或是等价的。此外异或满足区间减性质。

因为有修改，我们很自然地想到用数据结构维护。

最无脑的就是直接上树链剖分或是Splay维护区间xor值即可。

仔细想一想，发现可以利用LCA消去“树上路径”，转化为根到x路径上求xor值。

我们可以很经典地直接使用线段树或树状数组维护dfs序。

有一个很强的trick就是权值可以为0！

所以比如路径上有3个0，虽然他们xor值还是0，但是他们是出现了奇数次。

我特意把A[i]说成∈自然数集而不是[0,100000][0,100000][0,100000]，就是想尽量不被发现。

怎么避免呢？单独维护0的情况？

有一个很简单的解决方案：直接把读入时所有权值+1，输出的时候再-1即可！

时间复杂度为O(N∗log(N)2)或者O(N∗log(N))

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 const int maxn=1e5+;

 int rmq[maxn*];

 struct ST

 {

     int mm[*maxn];

     int dp[*maxn][];

     void init(int n)

     {

         mm[]=-;

         for ( int i=;i<=n;i++ )

         {

             mm[i]=((i&(i-))==)?mm[i-]+:mm[i-];

             dp[i][]=i;

         }

         for ( int j=;j<=mm[n];j++ )

         {

             for ( int i=;i+(<<j)-<=n;i++ )

             {

                 if ( rmq[dp[i][j-]]<rmq[dp[i+(<<(j-))][j-]] ) dp[i][j]=dp[i][j-];

                 else dp[i][j]=dp[i+(<<(j-))][j-];

             }

         }

     }

     int query(int a,int b)

     {

         if ( a>b ) swap(a,b);

         int k=mm[b-a+];

         if ( rmq[dp[a][k]]<=rmq[dp[b-(<<k)+][k]] ) return dp[a][k];

         else return dp[b-(<<k)][k];

     }

 };

 struct Edge{

     int to,nxt;

 }edge[maxn*];

 int tot,head[maxn],in[maxn],out[maxn];

 int F[maxn],P[maxn],cnt,now,val[maxn];

 int bit[maxn*];

 ST st;

 int lowbit(int x)

 {

     return x&(-x);

 }

 void add(int k,int num)

 {

     while ( k<maxn* )

     {

         bit[k]^=num;

         k+=lowbit(k);

     }

 }

 int sum(int k)

 {

     int s=;

     while ( k )

     {

         s^=bit[k];

         k-=lowbit(k);

     }

     return s;

 }

 void init()

 {

     tot=;

     memset(head,-,sizeof(head));

 }

 void addedge(int u,int v)

 {

     edge[tot].to=v;

     edge[tot].nxt=head[u];

     head[u]=tot++;

 }

 void dfs(int u,int pre,int dep)

 {

     F[++cnt]=u;

     in[u]=++now;

     rmq[cnt]=dep;

     P[u]=cnt;

     for ( int i=head[u];i!=-;i=edge[i].nxt )

     {

         int v=edge[i].to;

         if ( v==pre ) continue;

         dfs(v,u,dep+);

         F[++cnt]=u;

         rmq[cnt]=dep;

     }

     out[u]=++now;

 }

 void LCA_init(int root,int num)

 {

     cnt=;

     now=;

     dfs(root,root,);

     st.init(*num-);

 }

 int query(int u,int v)

 {

     return F[st.query(P[u],P[v])];

 }

 bool flag[maxn];

 int main()

 {

     int T,u,v,q,op,N;

     scanf("%d",&T);

     while ( T-- )

     {

         scanf("%d%d",&N,&q);

         init();

         memset(flag,false,sizeof(flag));

         memset(bit,,sizeof(bit));

         for ( int i=;i<N;i++ )

         {

             scanf("%d%d",&u,&v);

             addedge(u,v);

             addedge(v,u);

             flag[v]=true;

         }

         int root;

         for ( int i=;i<=N;i++ )

         {

             if ( !flag[i] )

             {

                 root=i;

                 break;

             }

         }

         LCA_init(root,N);

         for ( int i=;i<=N;i++ )

         {

             scanf("%d",&val[i]);

             val[i]++;

             add(in[i],val[i]);

             add(out[i],val[i]);

         }

         //for ( int i=1;i<=N;i++ ) printf("%d %d\n",in[i],out[i]);

         //for ( int i=1;i<=2*N;i++ ) printf("%d\n",sum(i));

         while ( q-- )

         {

             scanf("%d%d%d",&op,&u,&v);

             if ( op== )

             {

                 v++;

                 add(in[u],val[u]^v);

                 add(out[u],val[u]^v);

                 val[u]=v;

             }

             else

             {

                 int l=query(u,v);

                 int ans=sum(in[u])^sum(in[v])^val[l];

                 if ( ans== ) printf("-1\n");

                 else printf("%d\n",ans-);

             }

         }

         //for ( int i=1;i<=N;i++ ) printf("%d %d\n",in[i],out[i]);

         //for ( int i=1;i<=2*N;i++ ) printf("%d\n",sum(i));

     }

     return ;

 }

HDOJ5274（WA）

 #pragma comment(linker, "/STACK:102400000,102400000")

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<vector>

 #include<algorithm>

 using namespace std;

 #define MAXN 100005

 #define MAXM 300005

 #define LOG 19

 #define lowbit(i) (i & -i)

 vector<int>vec[MAXN];

 int _,n,q,cnt;

 int val[MAXN],uid[MAXN],vid[MAXN],dp[LOG][MAXM],pre[MAXM];

 void modify(int i,int v)

 {

     for(;i < MAXM;i += lowbit(i))

         pre[i] ^= v;

 }

 int sum(int i)

 {

     int ans = ;

     for(;i;i -= lowbit(i))

         ans ^= pre[i];

     return ans;

 }

 void dfs(int u,int fa)

 {

     for(int i = ;i < vec[u].size();i++)

     {

         int v = vec[u][i];

         if(v == fa)continue;

         uid[v] = ++cnt;

         modify(cnt,val[v]);

         dp[][cnt] = v;

         dfs(v,u);

         vid[v] = ++cnt;

         modify(cnt,val[v]);

         dp[][cnt] = u;

     }

 }

 void init_rmq()

 {

     for(int i = ;( << i) <= cnt;i++)

         for(int j = ;j + ( << i) -  <= cnt;j++)

             dp[i][j] = min(dp[i - ][j],dp[i - ][j + ( << i - )]);

 }

 int lca(int l,int r)

 {

     if(l > r)swap(l,r);

     int i = ;

     for(;l + ( << i) -  <= r;i++);

     i--;

     return min(dp[i][l],dp[i][r - ( << i) + ]);

 }

 int main()

 {

     scanf("%d",&_);

     while(_--)

     {

         scanf("%d%d",&n,&q);

         for(int i = ;i <= n;i++)vec[i].clear();

         vec[].push_back() , vec[].push_back();

         memset(pre,,sizeof(pre));

         for(int i = ;i < n;i++)

         {

             int u,v;

             scanf("%d%d",&u,&v);

             vec[u].push_back(v),vec[v].push_back(u);

         }

         for(int i = ;i <= n;i++)

         {

             scanf("%d",&val[i]);

             val[i]++;

         }

         cnt = ;

         dfs(,-);

         init_rmq();

         for(int i = ;i < q;i++)

         {

             int c,u,v;

             scanf("%d%d%d",&c,&u,&v);

             if(c == )

             {

                 v++;

                 modify(uid[u],val[u] ^ v);

                 modify(vid[u],val[u] ^ v);

                 val[u] = v;

             }

             else

             {

                 int fa = lca(uid[u],uid[v]);

                 int ans = sum(uid[u]) ^ sum(uid[v]) ^ val[fa];

                 if(!ans)puts("-1");

                 else printf("%d\n",ans - );

             }

         }

     }

 }

HDOJ5274（参考的AC代码）

6.（POJ2763）http://poj.org/problem?id=2763

题意：有一颗树，每条边都有自己的边权，起点在s，有q个询问，询问总共有两种操作

A:从当前点移动到x，输出所需要的时间 B：将通过边x的时间改为t

分析：利用RMQ计算LCA所用的，按DFS访问的顺序排列的顶点顺序。这样u到v之间的路径就是在序列中u和v之间的所有边减去往返重复的部分得到的结果。只要令沿叶子方向的边权为正，沿根方向的部分为负，于是有d(u,v)=d(LCA(u,v),u)+d(LCA(u,v),v)可以用bit进行计算

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 typedef long long ll;

 const int maxn=1e5+;

 int rmq[maxn*];

 struct ST

 {

     int mm[*maxn];

     int dp[*maxn][];

     void init(int n)

     {

         mm[] = -;

         for(int i = ;i <= n;i++)

         {

             mm[i] = ((i&(i-)) == )?mm[i-]+:mm[i-];

             dp[i][] = i;

         }

         for(int j = ; j <= mm[n];j++)

             for(int i = ; i + (<<j) -  <= n; i++)

                 dp[i][j] = rmq[dp[i][j-]] < rmq[dp[i+(<<(j-))][j-]]?dp[i][j-]:dp[i+(<<(j-))][j-];

     }

     int query(int a,int b)

     {

         if(a > b)swap(a,b);

         int k = mm[b-a+];

         return rmq[dp[a][k]] <= rmq[dp[b-(<<k)+][k]]?dp[a][k]:dp[b-(<<k)+][k];

     }

 };

 struct Edge{

     int to,nxt,w;

 }edge[maxn*];

 int tot,head[maxn];

 int F[maxn],P[maxn],cnt,n,es[maxn*];

 ll bit[maxn*];

 ST st;

 void init()

 {

     tot=;

     memset(head,-,sizeof(head));

     memset(bit,,sizeof(bit));

 }

 int lowbit(int x)

 {

     return x&(-x);

 }

 void add(int k,int num)

 {

     while ( k<=n )

     {

         bit[k]+=num;

         k+=lowbit(k);

     }

 }

 ll sum(int k)

 {

     ll sum_=;

     while ( k )

     {

         sum_+=bit[k];

         k-=lowbit(k);

     }

     return sum_;

 }

 void addedge(int u,int v,int w)

 {

     edge[tot].to=v;

     edge[tot].nxt=head[u];

     edge[tot].w=w;

     head[u]=tot++;

 }

 void dfs(int u,int pre,int dep)

 {

     F[++cnt]=u;

     rmq[cnt]=dep;

     P[u]=cnt;

     for ( int i=head[u];i!=-;i=edge[i].nxt )

     {

         int v=edge[i].to;

         int w=edge[i].w;

         if ( v==pre ) continue;

         es[i]=cnt+;

         add(es[i],w);

         dfs(v,u,dep+);

         F[++cnt]=u;

         es[i^]=cnt;

         add(es[i^],-w);

         rmq[cnt]=dep;

     }

 }

 void LCA_init(int root,int num)

 {

     cnt=;

     dfs(root,root,);

     st.init(*num-);

 }

 int query(int u,int v)

 {

     return F[st.query(P[u],P[v])];

 }

 bool flag[maxn];

 int main()

 {

     int T,N,q,s,u,v,w,op;

     while ( scanf("%d%d%d",&N,&q,&s)!=EOF )

     {

         init();

         n=*N-;

         memset(flag,false,sizeof(flag));

         for ( int i=;i<N;i++ )

         {

             scanf("%d%d%d",&u,&v,&w);

             addedge(u,v,w);

             addedge(v,u,w);

             flag[v]=true;

         }

         int root;

         for ( int i=;i<=N;i++ )

         {

             if ( !flag[i] )

             {

                 root=i;

                 break;

             }

         }

         LCA_init(root,N);

         u=s;

         //for ( int i=1;i<=n;i++ ) printf("%lld\n",sum(i));

         //for ( int i=0;i<2*(N-1);i++ ) printf("%d\n",es[i]);

         while ( q-- )

         {

             scanf("%d",&op);

             if ( op== )

             {

                 scanf("%d",&v);

                 int l=query(u,v);

                 printf("%lld\n",sum(P[u])+sum(P[v])-*sum(P[l]));

                 u=v;

             }

             else

             {

                 int p,x,k1,k2;

                 scanf("%d%d",&p,&x);

                 k1=es[(p-)*];

                 k2=es[((p-)*)^];

                 add(k1,x-edge[(p-)*].w);

                 add(k2,edge[((p-)*)^].w-x);

                 edge[(p-)*].w=edge[((p-)*)^].w=x;

             }

         }

         //for ( int i=1;i<=n;i++ ) printf("%lld\n",sum(i));

     }

     return ;

 }

POJ2763(WA)

注：以上两题通过与标程对拍也没找到错误的点，希望有人可以提供一下有用的数据，谢谢！

巴特西

专题训练之LCA

最新文章

热门文章