[Codeforces]852I - Dating-白红宇

[Codeforces]852I - Dating

阅读量：4470 次

发布时间：2019-06-08

本文共 1670 字，大约阅读时间需要 5 分钟。

题目大意：给定一棵n个点的树，每个点上有一个汉子或妹子，每人有一个权值，每次询问一条链上选出一对权值相等的男女有多少种选法。（n,q<=10^5）

做法：比较显然的树上莫队，熟悉序列莫队那套理论再推广到树上即可，我的树上莫队好像有点假，我是先树分块，对每块的根跑一遍dfs处理到各个点的链的信息并顺便处理一个端点在这个块内的询问，常数好像有点大，卡了半天常才过……学习了一下dalao的树上莫队，求一个进和出都算一遍的dfs序，链询问转化为区间询问，在区间内但不在链上的会被计算到两次所以被抵消了，感觉很奇妙。

丑陋代码：

#include
     
      #include
      
       #include
       
        #include
        using namespace std;char BB[1<<25],*S=BB;inline int read(){    int x;char c;    while((c=*S++)<'0'||c>'9');    for(x=c-'0';(c=*S++)>='0'&&c<='9';)x=x*10+c-'0';    return x;}#define MN 100000#define K 700struct edge{
   int nx,t;}e[MN*2+5];struct query{
   int x,y,id;}Q[MN+5];int a[MN+5],b[MN+5],cnt,h[MN+5],en,fa[MN+5],d[MN+5],f[MN+5],dep[MN+5];int rt,nw,u[MN+5],A[MN+5],B[MN+5];long long ans,C[MN+5];bool cmp(const query&a,const query&b){
   return f[a.x]
         
          
            mp;inline void ins(int x,int y){ e[++en]=(edge){h[x],y};h[x]=en; e[++en]=(edge){h[y],x};h[y]=en;}void dfs(int x){ for(int i=h[x];i;i=e[i].nx)if(e[i].t!=fa[x]) { fa[e[i].t]=x;dep[e[i].t]=dep[x]+1;dfs(e[i].t); d[x]=max(d[x],d[e[i].t]+1); } if(d[x]==K||x==rt)f[x]=x,d[x]=-1;}void build(int x){ for(int i=h[x];i;i=e[i].nx)if(e[i].t!=fa[x]) { if(!f[e[i].t])f[e[i].t]=f[x]; build(e[i].t); }}void DFS(int x,int fa){ d[x]=++cnt; for(int i=h[x];i;i=e[i].nx) if(e[i].t!=fa)DFS(e[i].t,x);}bool CMP(const query&a,const query&b){ return d[a.y]
           
            dep[Q[i].y]-dep[f[Q[i].y]])swap(Q[i].x,Q[i].y); } sort(Q+1,Q+q+1,cmp); for(nw=1;nw<=q;) { DFS(f[Q[nw].x],cnt=0); for(i=nw;f[Q[i].x]==f[Q[nw].x];++i); sort(Q+nw,Q+i,CMP); solve(rt=f[Q[nw].x],ans=0); } for(i=1;i<=q;++i)printf("%I64d\n",C[i]);}

转载于:https://www.cnblogs.com/ditoly/p/CF852I.html

你可能感兴趣的文章

超简单的listview单选模式SingleMode（自定义listview item）