SPOJ- QTREE+HDU 3966（树链剖分裸题

题目：维护一个树，支持修改边长，查询任意两点间距离。

思路：学习了一下树链剖分，还是看了一阵子才看懂的（大概两个多小时orz。。。）其实总的来说并不是很难，主要是数组比较多，然后看的那篇博客大概是为了压缩代码写得比较紧凑所以看的不是很明白。树链剖分的比较有技巧性的地方是查询，如果在一条轻链上，每次往上一条边，如果是在重链上，就是区间查询。树链剖分保证任意路径上的重链和轻链条数是logn的，所以总的复杂度就是logn的。这个题是单点更新，所以线段树方面没什么难度。

/* *@author: Cwind *http://www.cnblogs.com/Cw-trip/ */ #include <bits/stdc++.h> #define pb push_back #define PB pop_back #define bk back() #define se second #define fs first #define IINF (1<<29) #define sq(x) (x)*(x) #define eps 0.000000001 #define clr(x) memset((x),0,sizeof (x)) using namespace std; typedef long long ll; typedef pair<ll,ll> P;/////Segment Tree const int maxp=1e5; const int maxv=1e4+300; struct Node {int l,r;int val;Node *ch[2]; }pool[maxp]; int ph=0; inline Node *newNode(){Node *n=&pool[ph++];n->val=0;return n; } void seg_build(Node *n,int l,int r){n->l=l,n->r=r;if(r-l<=1) return;int mid=(r+l)/2;n->ch[0]=newNode();n->ch[1]=newNode();seg_build(n->ch[0],l,mid);seg_build(n->ch[1],mid,r); } void seg_update(Node *n,int a,int b,int x){int l=n->l,r=n->r;if(l>=b||r<=a) return;if(r-l<=1){n->val=x;return;}seg_update(n->ch[0],a,b,x);seg_update(n->ch[1],a,b,x);n->val=max(n->ch[0]->val,n->ch[1]->val); } int seg_query(Node *n,int a,int b){int l=n->l,r=n->r;if(l>=b||r<=a) return 0;if(l>=a&&r<=b) return n->val;return max(seg_query(n->ch[0],a,b),seg_query(n->ch[1],a,b)); } Node *root; void seg_init(){ph=0;root=newNode(); }///Tree Cut struct EDGE{int to,d;int id;EDGE(int to,int d,int id):to(to),d(d),id(id){} }; vector<EDGE> G[maxv]; int fa[maxv],dep[maxv],siz[maxv],son[maxv],top[maxv],w[maxv],itow[maxv],sone[maxv]; void dfs1(int v,int d,int f=-1){dep[v]=d;fa[v]=f;siz[v]=1;int maxs=0;son[v]=0;for(int i=0;i<G[v].size();i++){EDGE &e=G[v][i];if(e.to==f) continue;dfs1(e.to,d+1,v);siz[v]+=siz[e.to];if(siz[e.to]>maxs){son[v]=e.to;maxs=siz[e.to];sone[v]=e.id;}} } int dfsn=0; int dd[maxv]; void dfs2(int v,int ff,int from){w[v]=dfsn++;itow[from]=w[v];if(ff==-1) top[v]=v;else top[v]=top[ff];if(son[v])dfs2(son[v],v,sone[v]);for(int i=0;i<G[v].size();i++){EDGE &e=G[v][i];if(e.to==fa[v]||e.to==son[v]) continue;dfs2(e.to,-1,e.id);} } int T,N; void build_tree(){for(int i=1;i<N;i++){seg_update(root,itow[i],itow[i]+1,dd[i]);} }int Query(int a,int b){int f1=top[a],f2=top[b],ans=0;while(f1!=f2){if(dep[f1]>dep[f2]) swap(a,b),swap(f1,f2);ans=max(ans,seg_query(root,w[f2],w[b]+1));b=fa[f2];f2=top[b];}if(a==b) return ans;if(dep[a]>dep[b]) swap(a,b);ans=max(ans,seg_query(root,w[a]+1,w[b]+1));return ans; } char r[maxv]; int main(){freopen("/home/files/CppFiles/in","r",stdin);//freopen("defense.in","r",stdin);//freopen("defense.out","w",stdout);cin>>T;while(T--){cin>>N;for(int i=1;i<=N;i++) G[i].clear();dfsn=0;seg_init();seg_build(root,1,N);for(int i=1;i<=N-1;i++){int a,b,c;scanf("%d%d%d",&a,&b,&c);G[a].pb(EDGE(b,c,i));G[b].pb(EDGE(a,c,i));dd[i]=c;}dfs1(1,0);dfs2(1,-1,0);seg_build(root,1,N);build_tree();for(;;){scanf("%s",r);if(r[0]=='D') break;if(r[0]=='C'){int a,b;scanf("%d%d",&a,&b);seg_update(root,itow[a],itow[a]+1,b);}else{int a,b;scanf("%d%d",&a,&b);printf("%d\n",Query(a,b));}}}return 0; } View Code

ps：t了，差点开始怀疑是线段树写挫了。。结果是死循环了。。。

 hdu3966

题目：维护一棵树上的点权，给某两点间的路径上的所有点加上权值x，询问某个点的点权。

思路：由于是直接询问点，所以实际上比spoj的那道题好写，区间和直接用bit维护一下就好了。

/* *@author: Cwind *http://www.cnblogs.com/Cw-trip/ */ #include <bits/stdc++.h> #define pb push_back #define PB pop_back #define bk back() #define se second #define fs first #define IINF (1<<29) #define sq(x) (x)*(x) #define eps 0.000000001 #define clr(x) memset((x),0,sizeof (x)) using namespace std; typedef long long ll; typedef pair<ll,ll> P;const int maxn=5e4+300; int N,M,O; int a[maxn]; vector<int> G[maxn]; /////Tree Cut int fa[maxn],dep[maxn],son[maxn],top[maxn],siz[maxn],tw[maxn]; void dfs1(int v,int d=0,int f=-1){fa[v]=f;siz[v]=1;dep[v]=d;son[v]=0;int ma=0;for(int i=0;i<G[v].size();i++){int u=G[v][i];if(u==f) continue;dfs1(u,d+1,v);siz[v]+=siz[u];if(siz[u]>ma){ma=siz[u];son[v]=u;}} } int dfsn=0; void dfs2(int v){if(fa[v]==-1) top[v]=v;tw[v]=++dfsn;if(son[v]){top[son[v]]=top[v];dfs2(son[v]);}for(int i=0;i<G[v].size();i++){int u=G[v][i];if(u==fa[v]||u==son[v]) continue;top[u]=u;dfs2(u);} } /BIT const int maxB=maxn*2; struct BIT{int a[maxB],b[maxB];void clear(){memset(a,0,sizeof a);memset(b,0,sizeof b);}void add(int *A,int p,int x){while(p<maxB){A[p]+=x;p+=p&-p;}}int sum(int *A,int p){int ans=0;while(p){ans+=A[p];p-=p&-p;}return ans;}void seg_add(int l,int r,int x){add(a,l,-x*(l-1));add(b,l,x);add(a,r+1,x*r);add(b,r+1,-x);}int get(int p){int s1=sum(b,p-1)*(p-1)+sum(a,p-1);int s2=sum(b,p)*(p)+sum(a,p);return s2-s1;} }B;void update(int v1,int v2,int x){int f1=top[v1],f2=top[v2];while(f1!=f2){if(dep[f1]>dep[f2]) swap(v1,v2),swap(f1,f2);B.seg_add(tw[f2],tw[v2],x);v2=fa[f2],f2=top[v2];}if(dep[v1]>dep[v2]) swap(v1,v2);B.seg_add(tw[v1],tw[v2],x); } char r[10]; int main(){freopen("/home/files/CppFiles/in","r",stdin);//freopen("defense.in","r",stdin);//freopen("defense.out","w",stdout);while(cin>>N>>M>>O){dfsn=0;B.clear();for(int i=0;i<maxn;i++)G[i].clear();for(int i=1;i<=N;i++)scanf("%d",&a[i]);for(int i=0;i<M;i++){int u,v;scanf("%d%d",&u,&v);G[u].pb(v);G[v].pb(u);}dfs1(1);dfs2(1);for(int i=1;i<=N;i++)B.seg_add(tw[i],tw[i],a[i]);while(O--){scanf("%s",r);int a,b,c;if(r[0]=='I'){scanf("%d%d%d",&a,&b,&c);update(a,b,c);}else if(r[0]=='D'){scanf("%d%d%d",&a,&b,&c);update(a,b,-c);}else{scanf("%d",&a);printf("%d\n",B.get(tw[a]));}}}return 0; } View Code

 

转载于:https://www.cnblogs.com/Cw-trip/p/4783758.html

总结

以上是生活随笔为你收集整理的SPOJ- QTREE+HDU 3966（树链剖分裸题的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。