# BZOJ 4012 HNOI2015 开店 动态树分治+二分

(茴香豆的茴有4种写法泥萌知道嘛…?

1.线段树保护虚树
2.点分治+线段树
3.分块

#include <vector> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define M 150100 #define B 400 using namespace std; typedef vector<pair<int,long long> > abcd; int n,m,A; int a[M]; long long last_ans; namespace Tree{ struct edge{ int to,f,next; bool ban; }table[M<<1]; int head[M],tot=1; int dpt[M],pos[M],T; int log_2[M<<1],min_dpt[M<<1][18]; void Add(int x,int y,int z) { table[++tot].to=y; table[tot].f=z; table[tot].next=head[x]; head[x]=tot; } void DFS(int x,int from) { int i; min_dpt[pos[x]=++T][0]=dpt[x]; for(i=head[x];i;i=table[i].next) if(table[i].to!=from) { dpt[table[i].to]=dpt[x]+table[i].f; DFS(table[i].to,x); min_dpt[++T][0]=dpt[x]; } } void Build_LCA() { int i,j; for(i=2;i<=T;i++) log_2[i]=log_2[i>>1]+1; for(j=1;j<=log_2[T];j++) for(i=1;i+(1<<j)-1<=T;i++) min_dpt[i][j]=min(min_dpt[i][j-1],min_dpt[i+(1<<j-1)][j-1]); } long long LCA_Depth(int x,int y) { x=pos[x];y=pos[y]; if(x>y) swap(x,y); int l=log_2[y-x+1]; return min(min_dpt[x][l],min_dpt[y-(1<<l)+1][l]); } long long Distance(int x,int y) { return dpt[x]+dpt[y]-2*LCA_Depth(x,y); } } pair<long long,int> operator + (const pair<long long,int> x,const pair<long long,int> y) { return make_pair(x.first+y.first,x.second+y.second); } pair<long long,int> operator - (const pair<long long,int> x,const pair<long long,int> y) { return make_pair(x.first-y.first,x.second-y.second); } /* struct Segtree{ Segtree *ls,*rs; long long sum1; int sum2; //sum1代表子树中所有点到该点的距离之和 //sum2代表子树中点的个数 void* operator new(size_t) { static Segtree *mempool,*C; if(C==mempool) mempool=(C=new Segtree[1<<15])+(1<<15); C->ls=C->rs=0x0; C->sum1=C->sum2=0; return C++; } friend void Insert(Segtree *&p,int x,int y,int pos,int val) { int mid=x+y>>1; if(!p) p=new Segtree; p->sum1+=val; p->sum2++; if(x==y) return ; if(pos<=mid) Insert(p->ls,x,mid,pos,val); else Insert(p->rs,mid+1,y,pos,val); } pair<long long,int> Query(Segtree *p,int x,int y,int l,int r) { int mid=x+y>>1; if(!p) return make_pair(0ll,0); if(x==l&&y==r) return make_pair(p->sum1,p->sum2); if(r<=mid) return Query(p->ls,x,mid,l,r); if(l>mid) return Query(p->rs,mid+1,y,l,r); return Query(p->ls,x,mid,l,mid) + Query(p->rs,mid+1,y,mid+1,r); } }; */ namespace Dynamic_TDC{ using namespace Tree; abcd sum1[M],sum2[M]; int fa[M]; int Get_Size(int x,int from) { int i,re=1; for(i=head[x];i;i=table[i].next) if(!table[i].ban&&table[i].to!=from) re+=Get_Size(table[i].to,x); return re; } int Get_Centre_Of_Gravity(int x,int from,int size,int &cg) { int i,re=1,flag=true; for(i=head[x];i;i=table[i].next) if(!table[i].ban&&table[i].to!=from) { int temp=Get_Centre_Of_Gravity(table[i].to,x,size,cg); if(temp<<1>size) flag=false; re+=temp; } if(size-re<<1>size) flag=false; if(flag) cg=x; return re; } void DFS(int x,int from,int dpt,abcd &sum1,abcd &sum2) { int i; sum1.push_back(pair<int,long long>(a[x],dpt)); sum2.push_back(pair<int,long long>(a[x],dpt)); for(i=head[x];i;i=table[i].next) if(!table[i].ban&&table[i].to!=from) DFS(table[i].to,x,dpt+table[i].f,sum1,sum2); } int Tree_Divide_And_Conquer(int x) { abcd::iterator it; int i,j,size=Get_Size(x,0); Get_Centre_Of_Gravity(x,0,size,x); sum1[x].push_back(pair<int,long long>(a[x],0)); for(i=head[x];i;i=table[i].next) if(!table[i].ban) { table[i].ban=table[i^1].ban=true; abcd temp; DFS(table[i].to,0,table[i].f,temp,sum1[x]); int y=Tree_Divide_And_Conquer(table[i].to); sum2[y]=temp;fa[y]=x; sum2[y].push_back(pair<int,long long>(-1,0)); sort(sum2[y].begin(),sum2[y].end()); for(j=1;j<sum2[y].size();j++) sum2[y][j].second+=sum2[y][j-1].second; } sum1[x].push_back(pair<int,long long>(-1,0)); sort(sum1[x].begin(),sum1[x].end()); for(j=1;j<sum1[x].size();j++) sum1[x][j].second+=sum1[x][j-1].second; return x; } pair<long long,int> Query(abcd &a,int l,int r) { if(a.empty()) return pair<long long,int>(0,0); abcd::iterator it1=lower_bound(a.begin(),a.end(),pair<int,long long>(l,0)); abcd::iterator it2=lower_bound(a.begin(),a.end(),pair<int,long long>(r+1,0)); it1--;it2--; return make_pair(it2->second-it1->second,it2-it1); } long long Query(int x,int l,int r) { int i; long long re=Query(sum1[x],l,r).first; for(i=x;fa[i];i=fa[i]) { pair<long long,int> temp=Query(sum1[fa[i]],l,r)-Query(sum2[i],l,r); re+=temp.first+temp.second*Distance(x,fa[i]); } return re; } } int main() { using namespace Tree; using namespace Dynamic_TDC; int i,x,y,z; cin>>n>>m>>A; for(i=1;i<=n;i++) scanf("%d",&a[i]); for(i=1;i<n;i++) { scanf("%d%d%d",&x,&y,&z); Add(x,y,z);Add(y,x,z); } DFS(1,0);Build_LCA(); Tree_Divide_And_Conquer(1); for(i=1;i<=m;i++) { scanf("%d%d%d",&x,&y,&z); y=(y+last_ans)%A; z=(z+last_ans)%A; if(y>z) swap(y,z); printf("%lld ",last_ans=Query(x,y,z)); } return 0; }

1. 本站所有资源来源于用户上传和网络，如有侵权请邮件联系站长！
2. 分享目的仅供大家学习和交流，您必须在下载后24小时内删除！
3. 不得使用于非法商业用途，不得违反国家法律。否则后果自负！
4. 本站提供的源码、模板、插件等等其他资源，都不包含技术服务请大家谅解！
5. 如有链接无法下载、失效或广告，请联系管理员处理！
6. 本站资源售价只是赞助，收取费用仅维持本站的日常运营所需！
7. 如遇到加密压缩包，请使用WINRAR解压,如遇到无法解压的请联系管理员！