N个节点的树，有R种属性，每个点属于一种属性。有Q次询问，每次询问r1,r2，回答有多少对(e1,e2)满足e1属性是r1，e2属性是r2，e1是e2的祖先。

数据规模

N≤200000,R≤25000，Q≤200000

30%数据R≤500

55%数据同种属性节点个数≤500

 

Input

 

Output

 

Sample Input

6 3 4

1

1 2

1 3

2 3

2 3

5 1

1 2

1 3

2 3

3 1

Sample Output

1

3

2

1

 

 

思路： 

这题我采用了一点分块算法，根据我的测试，题目好像没有r1=r2的情况。  

 

对于r2的颜色出现次数小于500的情况，我们可以暴力解决， 时间复杂复$O(500*n)$

 

对于r2的颜色出现超过500次的情况，由于这样的颜色不会超过400个，所以我们分块统计每个块里面这种颜色有几个。  

 

son[i][j]表示第i块里面第j种颜色有几个。  

 

分块我采用的按照size分块的方法，构建了虚树，可以保证块的大小和联通，但是不能保证块的数量。  

 

块内暴力解决，块间采用一些预处理，由于需要map，我的时间复杂度几乎炸了。 

 

1 #include
       
          2 using namespace std;  3 #define mp  make_pair  4 #define pii  pair
        
           5 int const N = 200000 + 3;  6 int const sz = 1000;   7 struct edge {  8     int to, nt;  9 } e[N << 1]; 10 int n, r, q, ans[N], v[N], cnt, h[N], num[N], ct[N], bl[N], c[10000][500], nb, id[N], nc; 11 // 这里我们按照size分块 12 // v 表示每个点的颜色 13 // ans 表示答案 14 // num 表示每个颜色出现的次数，也表示分块以后每个块里面点的数量 15 // ct 表示每种颜色出现的次数 16 // bl 表示每个点分别属于哪个块 17 // c数组表示每个块里面超过sz的颜色的点的数量 18 // nb 表示块的数量 19 // id 表示超过sz的颜色的新编号 20 // nc表示超过sz的颜色的数量 21 // a vector表示小于等于sz的那些询问 22 // b 表示小于等于sz的那些询问的编号 23 // vex 记录哪个块里面有哪些点。 24 // H 记录虚树 25 // cp表示每一块的顶端节点 26 int H[N], tin[N], tout[N], sum, cp[N], son[10000][500],yl[N],tq,pos[N]; 27 vector
         
           a[N], b[N], vex[10000]; 28 map
          
            mat; 29 void add(int a, int b) { 30     e[++cnt].to = b; 31     e[cnt].nt = h[a]; 32     h[a] = cnt; 33 } 34 int Add(int a, int b) { 35     e[++cnt].to = b; 36     e[cnt].nt = H[a]; 37     H[a] = cnt; 38 } 39 void dfs(int x) { 40     num[v[x]]++; 41     if(ct[v[x]] <= sz) { 42         for(int i = 0; i < a[v[x]].size(); i++) { 43             int t = a[v[x]][i]; 44             ans[b[v[x]][i]] += num[t]; 45         } 46     } 47     for(int i = h[x]; i; i = e[i].nt) 48         dfs(e[i].to); 49     num[v[x]]--; 50 } 51 void dfs2(int x, int fa) { 52     tin[x] = ++sum; 53     if(num[bl[fa]] >= sz) { 54         nb++; 55         cp[nb] = x; 56         Add(bl[fa], nb); 57     } 58     bl[x] = nb; 59     num[nb]++; 60     if(ct[v[x]] > sz) 61         son[nb][id[v[x]]]++; 62     for(int i = h[x]; i; i = e[i].nt) 63         dfs2(e[i].to, x); 64     tout[x] = ++sum; 65 } 66 inline int ancestor(int x, int y) { 67     return tin[x] <= tin[y] && tout[y] <= tout[x]; 68 } 69 void dfs3(int x) { 70     for(int i = H[x]; i; i = e[i].nt) { 71         int s = e[i].to; 72         dfs3(s); 73         for(int j = 1; j <= nc; j++) 74             son[x][j] += son[s][j]; 75     } 76 } 77 void ask(int x) { 78     for(int i = 0; i < vex[x].size(); i++) { 79         for(int j = H[x]; j; j = e[j].nt) { 80             int a = vex[x][i]; 81             int b = cp[e[j].to]; 82             if(!ancestor(a, b)) 83                 continue; 84             for(int cl = 1; cl <= nc; cl++) { 85                 int t = mat[mp(v[a], pos[cl])]; 86                 if(!t) 87                     continue; 88                 ans[t] += son[e[j].to][cl]; 89             } 90         } 91     } 92     for(int i = H[x]; i; i = e[i].nt) 93         ask(e[i].to); 94 } 95 int main() { 96     scanf("%d%d%d", &n, &r, &q); 97     scanf("%d", &v[1]); 98     ct[v[1]]++; 99     for(int i = 2; i <= n; i++) {100         int x, y;101         scanf("%d%d", &x, &y);102         add(x, i);103         v[i] = y;104         ct[v[i]]++;105     }106     for(int i = 1; i <= r; i++)107         if(ct[i] > sz) {108             id[i] = ++nc;109             pos[nc]=i;110         }111     for(int i = 1; i <= q; i++) {112         int x, y;113         scanf("%d%d", &x, &y);114         if(mat.find(mp(x,y))==mat.end()) {115             mat[mp(x,y)]=++tq;116             a[y].push_back(x);117             b[y].push_back(tq);118         }119         yl[i]=mat[mp(x,y)];120     }121     cp[0] = 1;122     dfs(1);123     memset(num, 0, sizeof(num));124     dfs2(1, 1);125     for(int i = 1; i <= n; i++)126         vex[bl[i]].push_back(i);127     for(int i = 0; i <= nb; i++) {128         for(int j = 0; j < vex[i].size(); j++)129             for(int k = 0; k < vex[i].size(); k++) {130                 int x = v[vex[i][j]];131                 int y = v[vex[i][k]];132                 if(vex[i][j]==vex[i][k])133                     continue;134                 if(!ancestor(vex[i][j], vex[i][k]))135                     continue;136                 if(ct[y] <= sz)137                     continue;138                 int t = mat[mp(x, y)];139                 if(!t)140                     continue;141                 ans[t]++;142             }143     }144     dfs3(0);145     ask(0);146     for(int i = 1; i <= q; i++)147         printf("%d\n", ans[yl[i]]);148     return 0;149 }
          
         
        
       

 

本题的另外一种做法：  

那么的话 我们对询问 (a,b)按照 b 这种颜色在树上的出现次数分类 阈值设为$\sqrt{n}$

如果b出现次数小于那么$\sqrt{n}$我们暴力对每个为b的点询问一通

在dfs时边记录边询问可以做到 $O(q*\sqrt{n}) $ 

然后如果 b出现次数大于$\sqrt{n}$那么这种b最多只有$\sqrt{n}$种 那么我们暴力对每个为a的点询问一通 每个点最多要询问

$\sqrt{n}$个b,在dfs时边记录边询问可以做到$O(n\sqrt{n})$

时间复杂度 $O(n*\sqrt{n}+q*\sqrt{n})  $ 

 

但是，实际的效果是如果不加去重，跑的比我写的一塌糊涂的分块算法还要慢，这是什么情况，有谁能告诉我。  

 最后吐糟一下这题，貌似怎么写都能过。  

1 #include
       
         2 using namespace std; 3 int const N=200000+3; 4 int sz,cnt,n,r,q,num[N],sum[N],v[N],h1[N],h2[N],h[N],ans[N],f[N]; 5 map
        
         
          ,int >mat; 6 template
          
           void read(T &x) { 7     x=0; 8     char c=0; 9     while (!isdigit(c))10         c=getchar();11     while (isdigit(c))12         x=x*10+(c^48),c=getchar();13 }14 struct edge {15     int to,nt,id;16 } e[N<<2];17 18 void add(int a,int b) {19     e[++cnt].to=b;20     e[cnt].nt=h[a];21     h[a]=cnt;22 }23 void add1(int a,int b,int c) {24     e[++cnt].to=b;25     e[cnt].nt=h1[a];26     e[cnt].id=c;27     h1[a]=cnt;28 }29 void add2(int a,int b,int c) {30     e[++cnt].to=b;31     e[cnt].nt=h2[a];32     e[cnt].id=c;33     h2[a]=cnt;34 }35 void dfs(int x) {36     num[v[x]]++;37     for(int i=h1[v[x]]; i; i=e[i].nt) {38         int t=e[i].to;39         ans[e[i].id]+=num[t];40     }41     for(int i=h[x]; i; i=e[i].nt)42         dfs(e[i].to);43     num[v[x]]--;44 }45 void dfs2(int  x) {46     num[v[x]]++;47     for(int i=h2[v[x]]; i; i=e[i].nt) {48         int t=e[i].to;49         ans[e[i].id]-=num[t];50     }51     for(int i=h[x]; i; i=e[i].nt)52         dfs2(e[i].to);53     for(int i=h2[v[x]]; i; i=e[i].nt) {54         int t=e[i].to;55         ans[e[i].id]+=num[t];56     }57 }58 59 int main() {60     scanf("%d%d%d",&n,&r,&q);61     scanf("%d",&v[1]);62     sum[v[1]]++;63     for(int i=2; i<=n; i++) {64         int x,y;65         read(x);66         read(y);67         v[i]=y;68         sum[y]++;69         add(x,i);70     }71     sz=sqrt(n);72     for(int i=1; i<=q; i++) {73         int x,y;74         read(x);75         read(y);76         f[i]=i;77         if(mat.find(make_pair(x,y))!=mat.end()) {78             f[i]=mat[make_pair(x,y)];79             continue;80         }81         mat[make_pair(x,y)]=i;82         if(sum[y]<=sz)83             add1(y,x,i);84         else85             add2(x,y,i);86     }87     dfs(1);88     dfs2(1);89     for(int i=1; i<=q; i++)90         printf("%d\n",ans[f[i]]);91     return 0;92 }