https://www.cnblogs.com/mountaink/p/9878918.html
分析：每次的选取必须选最优的一条链，那我们考虑一下选择这条链后，把这条路上的点的权值更新掉，再采取选最优的一条链的策略，如此往复。
所以考虑利用dfs序来处理线段树，线段树维护的是最最优链的值，已经这条链的链跟，的dfs序。
#include<bits/stdc++.h> using namespace std; #define lson root<<1,l,midd #define rson root<<1|1,midd+1,r typedef long long ll; const int M=2e5+5; struct node{ int v,nextt; }e[M<<1]; ll a[M],tree[M<<2],mp[M<<2],dis[M<<2],lazy[M<<2]; int dfn[M],fa[M],cnt,tot,head[M],vis[M],L[M],R[M]; void addedge(int u,int v){ e[cnt].v=v; e[cnt].nextt=head[u]; head[u]=cnt++; } void up(int root){ if(tree[root<<1]>tree[root<<1|1]){ tree[root]=tree[root<<1]; mp[root]=mp[root<<1]; } else{ tree[root]=tree[root<<1|1]; mp[root]=mp[root<<1|1]; } } void pushdown(int root){ if(lazy[root]){ ll c=lazy[root]; tree[root<<1]-=c; tree[root<<1|1]-=c; lazy[root<<1]+=c; lazy[root<<1|1]+=c; lazy[root]=0; } } void build(int root,int l,int r){ if(l==r){ tree[root]=dis[l],mp[root]=l; return ; } int midd=(l+r)>>1; build(lson); build(rson); up(root); } void update(int LL,int RR,ll c,int root,int l,int r){ if(LL<=l&&r<=RR){ tree[root]-=c; lazy[root]+=c; return ; } pushdown(root); int midd=(l+r)>>1; if(LL<=midd) update(LL,RR,c,lson); if(RR>midd) update(LL,RR,c,rson); up(root); } void dfs(int u,int f){ dfn[++tot]=u; L[u]=tot; dis[tot]=a[u]+dis[L[f]]; for(int i=head[u];~i;i=e[i].nextt){ int v=e[i].v; if(v==f) continue; dfs(v,u); } R[u]=tot; } int main(){ int n,k; memset(head,-1,sizeof(head)); scanf("%d%d",&n,&k); for(int i=1;i<=n;i++) scanf("%lld",&a[i]); for(int i=1;i<n;i++){ int u,v; scanf("%d%d",&u,&v); addedge(u,v); addedge(v,u); fa[v]=u; } int root=1; while(fa[root]) root=fa[root]; //cout<<root<<"~!!"<<endl; dfs(root,0); build(1,1,n); /* for(int i=1;i<=4*n;i++) cout<<dis[i]<<endl;*/ ll ans=0; int x; //cout<<"!!"<<endl; while(k--){ ans+=tree[1]; x=mp[1]; while(x&&!vis[x]){ update(L[dfn[x]],R[dfn[x]],a[dfn[x]],1,1,n); vis[x]=1; x=L[fa[dfn[x]]]; } } printf("%lld ",ans); return 0; }
http://acm.hdu.edu.cn/showproblem.php?pid=3887
题意：给出一树，求在以每个节点为跟的树中，有几个是比他小的？
分析：用dfs给树进行编号，然后从小到大输出答案（query，是询问俩个dfs序区间）并更新线段树，更新时，是单点更新，+1就行了，因为如果在查询比之前点深度浅的的位置，就肯定会包含比他深度深且是他的子树的dfs序区间
#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> #include<vector> using namespace std; #define lson root<<1,l,midd #define rson root<<1|1,midd+1,r const int M=5e5+5; int tree[M<<2],L[M],R[M],head[M],tot,cnt; struct node{ int v,nextt; }e[M]; void addedge(int u,int v){ e[cnt].v=v; e[cnt].nextt=head[u]; head[u]=cnt++; } void up(int root){ tree[root]=tree[root<<1]+tree[root<<1|1]; } void dfs(int u,int f){ L[u]=++tot; for(int i=head[u];~i;i=e[i].nextt){ int v=e[i].v; if(v==f) continue; dfs(v,u); } R[u]=tot; } void build(int root,int l,int r){ if(l==r){ tree[root]=0; return; } int midd=(l+r)>>1; build(lson); build(rson); } void update(int pos,int c,int root,int l,int r){ if(l==r){ tree[root]+=c; return ; } int midd=(l+r)>>1; if(pos<=midd) update(pos,c,lson); else update(pos,c,rson); up(root); } int query(int L,int R,int root,int l,int r){ if(L<=l&&r<=R){ return tree[root]; } int midd=(l+r)>>1; int ans=0; if(L<=midd) ans+=query(L,R,lson); if(R>midd) ans+=query(L,R,rson); return ans; } int main(){ int n,root; while(~scanf("%d%d",&n,&root)){ if(n==0&&root==0) break; tot=0,cnt=0; for(int i=0;i<=n;i++) head[i]=-1; memset(tree,0,sizeof(tree)); for(int i=1;i<n;i++){ int u,v; scanf("%d%d",&u,&v); addedge(u,v); addedge(v,u); } dfs(root,-1); build(1,1,n); for(int i=1;i<=n;i++){ printf("%d",query(L[i],R[i],1,1,n)); if(i==n) printf(" "); else printf(" "); update(L[i],1,1,1,n); } } return 0; }
http://poj.org/problem?id=3321
题意：给出一颗苹果树，起初每个节点点权为1，然后询问是以询问节点为根问有多少个苹果，更新是单点更新，1->0,0->1
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<vector> #define lson root<<1,l,midd #define rson root<<1|1,midd+1,r using namespace std; typedef long long ll; const int M=1e5+5; struct node{ int v,nextt; }e[M<<1]; int tree[M<<2],vis[M],L[M],R[M],cnt,tot,head[M]; void addedge(int u,int v){ e[cnt].v=v; e[cnt].nextt=head[u]; head[u]=cnt++; } void up(int root){ tree[root]=tree[root<<1]+tree[root<<1|1]; } void build(int root,int l,int r){ if(l==r){ tree[root]=1; return; } int midd=(l+r)>>1; build(lson); build(rson); up(root); } int query(int L,int R,int root,int l,int r){ if(L<=l&&r<=R){ return tree[root]; } int midd=(l+r)>>1; int ans=0; if(L<=midd) ans+=query(L,R,lson); if(R>midd) ans+=query(L,R,rson); return ans; } void update(int pos,int c,int root,int l,int r){ if(l==r){ tree[root]+=c; return ; } int midd=(l+r)>>1; if(pos<=midd) update(pos,c,lson); else update(pos,c,rson); up(root); } void dfs(int u,int f){ L[u]=++tot; for(int i=head[u];~i;i=e[i].nextt){ int v=e[i].v; if(v==f) continue; dfs(v,u); } R[u]=tot; } char s[2]; int main(){ int n; scanf("%d",&n); memset(head,-1,sizeof(head)); for(int i=1;i<n;i++){ int u,v; scanf("%d%d",&u,&v); addedge(u,v); addedge(v,u); } dfs(1,0); build(1,1,n); int m; scanf("%d",&m); while(m--){ int x; scanf("%s%d",s,&x); if(s[0]=='Q'){ printf("%d ",query(L[x],R[x],1,1,n)); } else{ if(vis[x]==0) update(L[x],-1,1,1,n),vis[x]=1; else update(L[x],1,1,1,n),vis[x]=0; } } return 0; }
http://codeforces.com/problemset/problem/620/E
分析：和数颜色的那道线段树题目差不多，只不过把树转化成dfs序而已。注意，在build时，要用dfn数组，而非L数组！！！！
#include<iostream> #include<cstring> #include<algorithm> #include<cstdio> #include<vector> #define lson root<<1,l,midd #define rson root<<1|1,midd+1,r using namespace std; typedef long long ll; const int M=4e5+5; struct node{ int v,nextt; }e[M<<1]; ll tree[M<<2],lazy[M<<2]; int L[M],R[M],head[M],tot,cnt,a[M],dfn[M]; void up(int root){ tree[root]=(tree[root<<1]|tree[root<<1|1]); } void pushdown(int root){ if(lazy[root]){ ll c=lazy[root]; lazy[root<<1]=c,lazy[root<<1|1]=c; tree[root<<1]=c,tree[root<<1|1]=c; lazy[root]=0ll; } } void build(int root,int l,int r){ if(l==r){ tree[root]=(1ll<<(a[dfn[l]]-1))*1ll; return ; } int midd=(l+r)>>1; build(lson); build(rson); up(root); } void update(int L,int R,int c,int root,int l,int r){ if(L<=l&&r<=R){ tree[root]=(1ll<<(c-1))*1ll; lazy[root]=(1ll<<(c-1))*1ll; return ; } pushdown(root); int midd=(l+r)>>1; if(L<=midd) update(L,R,c,lson); if(R>midd) update(L,R,c,rson); up(root); } ll query(int LL,int RR,int root,int l,int r){ if(LL<=l&&r<=RR){ return tree[root]; } ll ans=0; pushdown(root); int midd=(l+r)>>1; if(LL<=midd) ans|=query(LL,RR,lson); if(RR>midd) ans|=query(LL,RR,rson); up(root); return ans; } void dfs(int u,int f){ L[u]=++tot; dfn[tot]=u; for(int i=head[u];~i;i=e[i].nextt){ int v=e[i].v; if(v==f) continue; dfs(v,u); } R[u]=tot; } void addedge(int u,int v){ e[cnt].v=v; e[cnt].nextt=head[u]; head[u]=cnt++; } int sum(ll x){ int t=0; while(x){ if(x&1) t++; x>>=1; } return t; } int main(){ int n,m; memset(head,-1,sizeof(head)); scanf("%d%d",&n,&m); for(int i=1;i<=n;i++){ scanf("%d",&a[i]); } for(int i=1;i<n;i++){ int u,v; scanf("%d%d",&u,&v); addedge(u,v); addedge(v,u); } dfs(1,0); build(1,1,n); while(m--){ int op; scanf("%d",&op); if(op==1){ int x,y; scanf("%d%d",&x,&y); update(L[x],R[x],y,1,1,n); } else{ int x; scanf("%d",&x); printf("%d ",sum(query(L[x],R[x],1,1,n))); } } return 0; }