COJ 0346 WZJ的旅行（二）更新动态树分治版本

WZJ的旅行（二）

难度级别：D； 运行时间限制：3000ms； 运行空间限制：51200KB； 代码长度限制：2000000B

试题描述

时隔多日，WZJ又来到了幻想国旅行。幻想国由N个城市组成，由于道路翻修，只有N-1条双向道路可以通行，第i条双向道路从ui连接到vi，距离为wi。但这N-1条道路竟然连接了整个国家，每两个城市之间都有一条道路！ WZJ知道这里景点很多，所以他想从城市s出发到城市t，旅游所有沿途的城市。WZJ想起到锻炼作用，但又不想太累，所以城市s到城市t的距离必须在L到R之间。另外WZJ规定s必须小于t，你能帮助他统计有多少对城市（s,t）符合要求吗？

输入

第一行为三个正整数N,L,R。 接下来N-1行每行为三个正整数ui,vi,wi。

输出

输出多少对城市（s,t）符合要求。

输入示例

5 3 6 1 2 3 2 3 3 3 4 2 4 5 1

输出示例

6

其他说明

城市对(1,2)、（2,3）、(1,3)、(2,4)、(2,5)、（3,5）均符合要求，共计6对 1<=N<=100000 1<=L<=R<=10^9 1<=ui,vi<=N 1<=wi<=1000

题解：会写点分治了。。。

首先补集转换，不在同一个子树的 = 总的 - 在同一个子树的，那么就是求路径两段在同一个子树的，dfs一遍排序再金鸡独立大法求前缀，转成区间，然后就没了。

意会一下。。。（逃。。。

 #include<iostream>
 #include<cstdio>
 #include<cmath>
 #include<algorithm>
 #include<queue>
 #include<cstring>
 #define PAU putchar(' ')
 #define ENT putchar('\n')
 using namespace std;
 const int maxn=+,inf=-1u>>;
 struct ted{int x,y,w;ted*nxt;}adj[maxn<<],*fch[maxn],*ms=adj;
 void add(int w,int y,int x){
     *ms=(ted){x,y,w,fch[x]};fch[x]=ms++;
     *ms=(ted){y,x,w,fch[y]};fch[y]=ms++;
     return;
 }
 bool vis[maxn];
 int L,R,CG=,siz[maxn],f[maxn],n,size;
 void findcg(int x,int fa){
     int mxs=-inf;siz[x]=;
     for(ted*e=fch[x];e;e=e->nxt){
         int v=e->y;if(v!=fa&&!vis[v]){
             findcg(v,x);siz[x]+=siz[v];
             mxs=max(mxs,siz[v]);
         }
     }f[x]=max(mxs,size-siz[x]);
     if(f[x]<f[CG])CG=x;return;
 }
 long long ans;
 int A[maxn],dep[maxn],cnt;
 void dfs(int x,int fa,int dist){
     A[cnt++]=dist;
     for(ted*e=fch[x];e;e=e->nxt){
         int v=e->y;if(v!=fa&&!vis[v])dfs(v,x,dist+e->w);
     }return;
 }
 long long cal(int x,int base){
     cnt=;dfs(x,,base);long long res=;
     sort(A,A+cnt);
     int l=,r=cnt-;while(l<r)if(A[l]+A[r]>R)r--;else res+=r-l++;
     l=;r=cnt-;while(l<r)if(A[l]+A[r]>=L)r--;else res-=r-l++;
     return res;
 }
 void solve(int x){
     vis[x]=true;ans+=cal(x,);
     for(ted*e=fch[x];e;e=e->nxt){
         int v=e->y;if(!vis[v]){
             ans-=cal(v,e->w);
             f[CG=]=inf;size=siz[v];findcg(v,);
             solve(CG);
         }
     }return;
 }
 inline int read(){
     int x=,sig=;char ch=getchar();
     while(!isdigit(ch)){if(ch=='-') sig=-;ch=getchar();}
     while(isdigit(ch)) x=*x+ch-'',ch=getchar();
     return x*=sig;
 }
 inline void write(long long x){
     if(x==){putchar('');return;}if(x<) putchar('-'),x=-x;
     int len=;long long buf[];while(x) buf[len++]=x%,x/=;
     for(int i=len-;i>=;i--) putchar(buf[i]+'');return;
 }
 void init(){
     n=read();L=read();R=read();
     for(int i=;i<n;i++)add(read(),read(),read());
     f[CG=]=inf;size=n;findcg(,);
     solve(CG);write(ans);
     return;
 }
 void work(){
     return;
 }
 void print(){
     return;
 }
 int main(){
     init();work();print();return ;
 }

当然窝萌还可以写动态树分治对不对，维护两个treap就是常数有点大耶。

要注意一点：cal函数只需要query就行了，不需要重新计算一遍！！！

 #include<iostream>
 #include<cstdio>
 #include<cmath>
 #include<algorithm>
 #include<queue>
 #include<cstring>
 #include<ctime>
 #define PAU putchar(' ')
 #define ENT putchar('\n')
 #define CH for(int d=0;d<2;d++)if(ch[d])
 using namespace std;
 const int maxn=+,maxq=+,maxnode=+,maxm=+,inf=-1u>>;
 struct node{
     node*ch[];int r,siz,v;
     void init(){r=rand();siz=;ch[]=ch[]=NULL;return;}
     void update(){siz=;CH{siz+=ch[d]->siz;}return;}
 }treap[maxnode],*nodecnt=treap,*cha[maxn],*tre[maxn];
 node*newnode(){node*x=nodecnt++;x->init();return x;}
 void rotate(node*&x,int d){
     node*k=x->ch[d^];x->ch[d^]=k->ch[d];k->ch[d]=x;x->update();k->update();x=k;return;
 }
 void insert(node*&x,int v){
     if(!x)x=newnode(),x->v=v;
     else{int d=v>x->v;insert(x->ch[d],v);
         if(x->r<x->ch[d]->r)rotate(x,d^);else x->update();
     }return;
 }
 int find(node*x,int v){
     if(!x)return ;
     if(v<=x->v)return find(x->ch[],v);
     else return (x->ch[]?x->ch[]->siz:)++find(x->ch[],v);
 }
 struct ted{int x,y,w;ted*nxt;}adj[maxm],*fch[maxn],*ms=adj;
 void add(int x,int y,int w){
     *ms=(ted){x,y,w,fch[x]};fch[x]=ms++;
     *ms=(ted){y,x,w,fch[y]};fch[y]=ms++;
     return;
 }
 int mi[maxq][],Log[maxq],dep[maxn],pos[maxn],cnt;
 void build(int x,int fa,int dis){
     mi[++cnt][]=dep[x]=dis;pos[x]=cnt;
     for(ted*e=fch[x];e;e=e->nxt){
         int v=e->y;if(v!=fa)build(v,x,dis+e->w),mi[++cnt][]=dep[x];
     }return;
 }
 void initrmq(){
     Log[]=-;for(int i=;i<=cnt;i++)Log[i]=Log[i>>]+;
     for(int j=;(<<j)<=cnt;j++)
         for(int i=;i+(<<j)-<=cnt;i++)
             mi[i][j]=min(mi[i][j-],mi[i+(<<j-)][j-]);return;
 }
 int dist(int x,int y){
     int ans=dep[x]+dep[y];x=pos[x];y=pos[y];if(x>y)swap(x,y);
     int k=Log[y-x+];return ans-*min(mi[x][k],mi[y-(<<k)+][k]);
 }
 int CG,f[maxn],size,siz[maxn],fa[maxn];bool vis[maxn];
 void findcg(int x,int fa){
     siz[x]=;int mxs=;
     for(ted*e=fch[x];e;e=e->nxt){
         int v=e->y;if(v!=fa&&!vis[v]){
             findcg(v,x);siz[x]+=siz[v];mxs=max(mxs,siz[v]);
         }
     }f[x]=max(mxs,size-siz[x]);if(f[x]<f[CG])CG=x;return;
 }
 void dfs(int x,int fa){
     siz[x]=;
     for(ted*e=fch[x];e;e=e->nxt){
         int v=e->y;if(v!=fa&&!vis[v])dfs(v,x),siz[x]+=siz[v];
     }return;
 }
 void solve(int x=CG){
     vis[x]=true;
     for(ted*e=fch[x];e;e=e->nxt){
         int v=e->y;if(!vis[v]){
             dfs(v,x);f[CG=]=size=siz[v];findcg(v,x);fa[CG]=x;solve();
         }
     }return;
 }
 void update(int x){
     insert(tre[x],);
     for(int ret=x;fa[x];x=fa[x]){
         int d=dist(ret,fa[x]);
         insert(tre[fa[x]],d);insert(cha[x],d);
     }return;
 }
 int k;
 int query(int x){
     int ans=find(tre[x],k);
     for(int ret=x;fa[x];x=fa[x]){
         int d=dist(ret,fa[x]);
         ans+=find(tre[fa[x]],k-d)-find(cha[x],k-d);
     }return ans;
 }
 int n,L,R;
 int cal(int t){
     k=t+;int ans=;for(int i=;i<=n;i++)ans+=query(i);return ans;
 }
 inline int read(){
     int x=,sig=;char ch=getchar();
     while(!isdigit(ch)){if(ch=='-')sig=-;ch=getchar();}
     while(isdigit(ch))x=*x+ch-'',ch=getchar();
     return x*=sig;
 }
 inline void write(int x){
     if(x==){putchar('');return;}if(x<)putchar('-'),x=-x;
     int len=,buf[];while(x)buf[len++]=x%,x/=;
     for(int i=len-;i>=;i--)putchar(buf[i]+'');return;
 }
 void init(){
     srand(time());
     n=read();L=read(),R=read();int x,y;
     for(int i=;i<n;i++)x=read(),y=read(),add(x,y,read());build(,,);initrmq();
     f[CG=]=size=n;findcg(,);solve();for(int i=;i<=n;i++)update(i);
     write((cal(R)-cal(L-))>>);
     return;
 }
 void work(){
     return;
 }
 void print(){
     return;
 }
 int main(){init();work();print();return ;}