HINT：

$1\leq N,Q\leq 10^5$

原题：CodeChef November Challenge 2013 - MONOPLOY

题解：

其实这题是【SDOI2017】树点涂色的弱化版。。。

然后树点涂色这题甚至是[LOJ6022]【BZOJ3779】重组病毒的弱化版。。。

首先题目中的距离就是求路径上不同颜色的数目；

容易发现修改操作看起来很像LCT里的轻重边切换，那么以dfs序为下标建一颗线段树维护每个点到根节点的距离和，外面用一颗LCT维护，每次access轻重边切换的时候在线段树上修改即可。

时间复杂度：$O(nlog^2n)$

1A就是爽

代码：

 #include<algorithm>

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<cmath>

 #include<queue>

 #define inf 2147483647

 #define eps 1e-9

 using namespace std;

 typedef long long ll;

 struct edge{

     int v,next;

 }a[];

 int n,q,u,v,x,tim=,tot=,head[],dep[],siz[],in[],out[],nmd[];

 char op[];

 namespace sgt{

     struct node{

         ll v,laz;

     }t[];

     void pd(int u,int l,int r){

         if(t[u].laz){

             int mid=(l+r)/;

             t[u*].v+=t[u].laz*(mid-l+);

             t[u*].laz+=t[u].laz;

             t[u*+].v+=t[u].laz*(r-mid);

             t[u*+].laz+=t[u].laz;

             t[u].laz=;

         }

     }

     void build(int l,int r,int u){

         if(l==r){

             t[u].v=dep[nmd[l]]-;

             return;

         }

         int mid=(l+r)/;

         build(l,mid,u*);

         build(mid+,r,u*+);

         t[u].v=t[u*].v+t[u*+].v;

     }

     void updata(int l,int r,int u,int L,int R,ll v){

         if(L<=l&&r<=R){

             t[u].v+=v*(r-l+);

             t[u].laz+=v;

             return;

         }

         int mid=(l+r)/;

         pd(u,l,r);

         if(L<=mid)updata(l,mid,u*,L,R,v);

         if(mid<R)updata(mid+,r,u*+,L,R,v);

         t[u].v=t[u*].v+t[u*+].v;

     }

     ll query(int l,int r,int u,int L,int R){

         if(L<=l&&r<=R){

             return t[u].v;

         }

         int mid=(l+r)/;

         ll ret=;

         pd(u,l,r);

         if(L<=mid)ret=query(l,mid,u*,L,R);

         if(mid<R)ret+=query(mid+,r,u*+,L,R);

         return ret;

     }

 }

 namespace lct{

     struct node{

         int son[],fa,v;

     }t[];

     bool ntrt(int u){

         return t[t[u].fa].son[]==u||t[t[u].fa].son[]==u;

     }

     bool lr(int u){

         return t[t[u].fa].son[]==u;

     }

     void rotate(int u){

         int f=t[u].fa,ff=t[f].fa,ch=lr(u);

         if(ntrt(f))t[ff].son[lr(f)]=u;

         t[f].son[ch]=t[u].son[ch^];

         t[t[f].son[ch]].fa=f;

         t[u].son[ch^]=f;

         t[f].fa=u;

         t[u].fa=ff;

     }

     void splay(int u){

         //printf("in splay %d %d\n",u,t[u].fa);

         while(ntrt(u)){

             int f=t[u].fa;

             if(ntrt(f))rotate(lr(u)^lr(f)?f:u);

             rotate(u);

         }

     }

     int get(int u){

         while(t[u].son[])u=t[u].son[];

         return u;

     }

     void access(int u){

         for(int now=;u;now=u,u=t[u].fa){

             //printf("%d %d\n",u,now);

             splay(u);

             if(t[u].son[]){

                 int x=get(t[u].son[]);

                 sgt::updata(,n,,in[x],out[x],);

             }

             if(now){

                 int x=get(now);

                 sgt::updata(,n,,in[x],out[x],-);

             }

             t[u].son[]=now;

         }

     }

 }

 void add(int u,int v){

     a[++tot].v=v;

     a[tot].next=head[u];

     head[u]=tot;

 }

 void dfs(int u,int fa,int dpt){

     dep[u]=dpt;

     siz[u]=;

     in[u]=++tim;

     nmd[tim]=u;

     for(int tmp=head[u];tmp!=-;tmp=a[tmp].next){

         int v=a[tmp].v;

         if(v!=fa){

             lct::t[v].fa=u;

             dfs(v,u,dpt+);

             siz[u]+=siz[v];

         }

     }

     out[u]=tim;

 }

 int main(){

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

     scanf("%d",&n);

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

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

         u++,v++;

         add(u,v);

         add(v,u);

     }

     dfs(,,);

     sgt::build(,n,);

     scanf("%d",&q);

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

         scanf("%s%d",op,&x);

         x++;

         if(op[]=='O')lct::access(x);

         else printf("%.8lf\n",(double)sgt::query(,n,,in[x],out[x])/(double)(siz[x]));

     }

     return ;

 }

巴特西

（WC2016模拟十八）Gangsters of Treeland

HINT：

题解：

代码：

最新文章

热门文章