| 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 ;}