首页 > 搜索 > DFS搜索 > HDU 4822-Tri-war-DFS-[解题报告]HOJ
2015
09-18

HDU 4822-Tri-war-DFS-[解题报告]HOJ

Tri-war

问题描述 :

Three countries, Red, Yellow, and Blue are in war. The map of battlefield is a tree, which means that there are N nodes and (N �C 1) edges that connect all the nodes. Each country has a base station located in one node. All three countries will not place their station in the same node. And each country will start from its base station to occupy other nodes. For each node, country A will occupy it iff other two country’s base stations have larger distances to that node compared to country A. Note that each edge is of the same length.

Given three country’s base station, you task is to calculate the number of nodes each country occupies (the base station is counted).

输入:

The input starts with a single integer T (1 ≤ T ≤ 10), the number of test cases.

Each test cases starts with a single integer N (3 ≤ N ≤ 10 ^ 5), which means there are N nodes in the tree.

Then N – 1 lines follow, each containing two integers u and v (1 ≤ u, v ≤ N, u ≠ v), which means that there is an edge between node u and node v.

Then a single integer M (1 ≤ M ≤ 10 ^ 5) follows, indicating the number of queries.

Each the next M lines contains a query of three integers a, b, c (1 ≤ a, b, c ≤ N, a, b, c are distinct), which indicates the base stations of the three countries respectively.

输出:

The input starts with a single integer T (1 ≤ T ≤ 10), the number of test cases.

Each test cases starts with a single integer N (3 ≤ N ≤ 10 ^ 5), which means there are N nodes in the tree.

Then N – 1 lines follow, each containing two integers u and v (1 ≤ u, v ≤ N, u ≠ v), which means that there is an edge between node u and node v.

Then a single integer M (1 ≤ M ≤ 10 ^ 5) follows, indicating the number of queries.

Each the next M lines contains a query of three integers a, b, c (1 ≤ a, b, c ≤ N, a, b, c are distinct), which indicates the base stations of the three countries respectively.

样例输入:

1
9
1 2
1 3
1 4
2 5
2 6
2 7
6 8
6 9
2
1 2 8
2 1 4

样例输出:

3 3 1
6 2 1

首先如果是两个点那应该从中间切成两半,再判断所属

所以必然需要使用树上倍增==

继而如果是三个点,则需要仔细分情况讨论==

参考别人的分类讨论写的,感觉那个type判断在哪条链很巧妙啊~

 #pragma comment(linker,"/STACK:16777216")
 #include<stdio.h>
 #include<string.h>
 #include<algorithm>
 using namespace std;
 struct dian{
   int type,u;
 };
 int now,next[200005],head[200005],point[200005];
 int parent[200005][21],size[200005],depth[200005];
 void add(int x,int y)
 {
   next[++now]=head[x];
   head[x]=now;
   point[now]=y;
 }
 void dfs(int u,int pre,int deep)
 {
   int i,v;
   parent[u][0]=pre;
   size[u]=1;
   depth[u]=deep;
   for (i=head[u];i!=-1;i=next[i])
   {
     v=point[i];
     if (v==pre) continue;
     dfs(v,u,deep+1);
     size[u]+=size[v];
   }
 }
 void rmq_build(int n)
 {
   for (int k=0;k<20;k++)
     for (int u=1;u<=n;u++)
       if (parent[u][k]==-1) parent[u][k+1]=-1;
       else parent[u][k+1]=parent[parent[u][k]][k];
 }
 int go_up(int u,int deep)
 {
   for (int k=0;k<=20;k++)
     if ((deep>>k)&1) u=parent[u][k];
   return u;
 }
 int rmq_query(int u,int v)
 {
   if (depth[u]<depth[v]) swap(u,v);
   u=go_up(u,depth[u]-depth[v]);
   if (u==v) return u;
   for (int k=20;k>=0;k--)
     if (parent[u][k]!=parent[v][k])
       u=parent[u][k],v=parent[v][k];
   return parent[u][0];
 }
 dian get_middle(int a,int b,int ab)
 {
   int len=depth[a]+depth[b]-2*depth[ab];
   dian n1;
   if (depth[a]>=depth[b])
     n1.type=1,n1.u=go_up(a,(len-1)/2);
   else n1.type=2,n1.u=go_up(b,len/2);
   return n1;
 }
 int n;
 int cal(int a,int b,int c,int ab,int ac)
 {
   dian ab_m=get_middle(a,b,ab),ac_m=get_middle(a,c,ac);
   if (ab_m.type==1&&ac_m.type==1)
     return depth[ab_m.u]>depth[ac_m.u]?size[ab_m.u]:size[ac_m.u];
   else if (ab_m.type==2&&ac_m.type==2){
       if (depth[ab_m.u]<depth[ac_m.u]) swap(ab_m,ac_m);
       if (rmq_query(ab_m.u,ac_m.u)==ac_m.u) return n-size[ac_m.u];
       return n-size[ab_m.u]-size[ac_m.u];
   }
   else{
     if (ab_m.type==2) swap(ab_m,ac_m);
     int tmp=rmq_query(ab_m.u,ac_m.u);
     if (tmp==ab_m.u) return size[ab_m.u]-size[ac_m.u];
     return size[ab_m.u];
   }
 }
 int main()
 {
   int a,b,c,ab,bc,ac,T,m,i;
   scanf("%d",&T);
   while (T--)
   {
     scanf("%d",&n);
     now=0;
     memset(head,-1,sizeof(head));
     for (i=1;i<n;i++)
     {
       scanf("%d%d",&a,&b);
       add(a,b); add(b,a);
     }
     dfs(1,-1,0);
     rmq_build(n);
     scanf("%d",&m);
     while (m--)
     {
       scanf("%d%d%d",&a,&b,&c);
       ab=rmq_query(a,b),ac=rmq_query(a,c),bc=rmq_query(b,c);
       printf("%d %d %d\n",
           cal(a,b,c,ab,ac),cal(b,a,c,ab,bc),cal(c,a,b,ac,bc));
     }
   }
   return 0;
 }

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4822

参考:http://www.cnblogs.com/xiao-xin/articles/4278317.html


,