PKU Online Judge 1054

Delayyy君很喜欢玩某个由Picks编写的方块游戏，游戏在一个由单位格组成的棋盘上进行。

游戏的主角是一个6个面互不相同的小方块，每次可以向上下左右中的某个方向翻滚一格。

棋盘上有 N 个关键格子，对应于游戏中的村庄，在坐标系中，每个村庄有一个坐标位置 (x,y) （任意两个村庄位置不相等）。

先前的方块村民已经修好了 N-1 条道路（高架桥、地下隧道等，即不能从一条道路走上另一条道路）使这 N 个村庄连通，并且由于方块民族的习俗，每条道路都平行于坐标轴。

主角小方块打算选两个村庄 S 、 T ，沿最短路进行一次 S 到 T 的旅行。

但由于方块民族的特殊属性，小方块一次旅行终止时必须和开始时的状态（即六个面的朝向）完全一致。

Delayyy君想知道，从每个村庄出发，主角小方块能选出多少个可行的旅行终点。

数据范围

1
1 1
3
1 1
1 2
5 1
1 2
1 3

0
1
0
1

#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
#define M 100050
#define E 1000000
#define mem(a,b) memset(a,b,sizeof(a))
struct node {int x,y,fx,fy,fz;
}p[M];
int head[M],next[E],edge_m,vec[E],ans[8][8][8];
int addedge(int s,int e){next[edge_m]=head[s],vec[edge_m]=e,head[s]=edge_m++;next[edge_m]=head[e],vec[edge_m]=s,head[e]=edge_m++;return 0;
}
int dfs(int now,int pre,int x,int y,int z){p[now].fx=x,p[now].fy=y,p[now].fz=z;ans[x][y][z]++;for(int i=head[now];i!=-1;i=next[i]){int g=vec[i];if(g!=pre){int tx=x,ty=y,tz=z,mx,my,mz;if(p[g].x!=p[now].x){int step=p[g].x-p[now].x;if(step>0){ty=y;step=step%4;for(;step;step--){mx=tx,mz=tz;tz=mx,tx=7-mz;}dfs(g,now,tx,ty,tz);}else {ty=y;step=(-step)%4;for(;step;step--){mx=tx,mz=tz;tz=7-mx,tx=mz;}dfs(g,now,tx,ty,tz);}}else {int step=p[g].y-p[now].y;if(step>0){tz=z;step=step%4;for(;step;step--){mx=tx,my=ty;ty=mx,tx=7-my;}dfs(g,now,tx,ty,tz);}else {tz=z;step=(-step)%4;for(;step;step--){mx=tx,my=ty;ty=7-mx,tx=my;}dfs(g,now,tx,ty,tz);}}}}return 0;
}
int main()
{int n,i,u,v;while(scanf("%d",&n)!=EOF){edge_m=0;mem(head,-1);mem(ans,0);for(i=1;i<=n;i++)scanf("%d%d",&p[i].x,&p[i].y);for(i=1;i<n;i++){scanf("%d%d",&u,&v);addedge(u,v);}dfs(1,-1,1,2,3);for(i=1;i<=n;i++)printf("%d\n",ans[p[i].fx][p[i].fy][p[i].fz]-1);}return 0;
}