题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=5044
题目大意：修改链上点，修改链上的边。查询所有点，查询所有边。
解题思路：
2014上海网赛的变态树链剖分模板题。将以往树链剖分的点&边修改和查询合在一起之后，难度上去不少。
第一个卡人点是读入优化。
第二个卡人点是树状数组。由于要查询所有点，如果使用线段树，每次都要扫到底层才能取出点值，必T无疑。
然后使用树状数组之后，树链剖分的点/边修改写法有些变动。
点查询变化不大。
边查询只要查询一下dep(u,v)大的那一端。
具体变化请仔细看代码。
#pragma comment(linker, "/STACK:1024000000,1024000000") #include "cstdio" #include "cstring" #include "iostream" using namespace std; #define maxn 100005 template <class T> inline bool read(T &ret) { char c; int sgn; if(c=getchar(),c==EOF) return 0; //EOF while(c!='-'&&(c<'0'||c>'9')) c=getchar(); sgn=(c=='-')?-1:1; ret=(c=='-')?0:(c-'0'); while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0'); ret*=sgn; return 1; } int s[maxn],dep[maxn],w[maxn],fa[maxn],top[maxn],son[maxn],tol,cnt,n,head[maxn]; struct Edge { int u,v,c; }edge[maxn]; struct EDGE { int next,to; }e[2*maxn]; void addedge(int u,int v) { e[tol].to=v; e[tol].next=head[u]; head[u]=tol++; } void dfs1(int u,int pre,int d) { s[u]=1;fa[u]=pre;dep[u]=d;son[u]=-1; for(int i=head[u];i!=-1;i=e[i].next) { int v=e[i].to; if(v==pre) continue; dfs1(v,u,d+1); s[u]+=s[v]; if(son[u]!=-1||s[v]>s[son[u]]) son[u]=v; } } void dfs2(int u,int tp) { w[u]=++cnt;top[u]=tp; if(son[u]!=-1) dfs2(son[u],tp); for(int i=head[u];i!=-1;i=e[i].next) { int v=e[i].to; if(v!=son[u]&&v!=fa[u]) dfs2(v,v); } } //Binary-Indexed-Tree type:0-point,1-edge int psum[maxn],esum[maxn]; inline int lowbit(int x) {return x&(-x);} int sum(int x,int type) { int ret=0; while(x>0) { if(!type) ret+=psum[x]; else ret+=esum[x]; x-=lowbit(x); } return ret; } void add(int x,int d,int type) { while(x<=n) { if(!type) psum[x]+=d; else esum[x]+=d; x+=lowbit(x); } } void p_Change(int x,int y,int v) { while(top[x]!=top[y]) { if(dep[top[x]]<dep[top[y]]) swap(x,y); add(w[top[x]],v,0); add(w[x]+1,-v,0); x=fa[top[x]]; } if(dep[x]>dep[y]) swap(x,y); add(w[x],v,0); add(w[y]+1,-v,0); } void e_Change(int x,int y,int v) { while(top[x]!=top[y]) { if(dep[top[x]]<dep[top[y]]) swap(x,y); add(w[top[x]],v,1); add(w[x]+1,-v,1); x=fa[top[x]]; } if(dep[x]>dep[y]) swap(x,y); if(x!=y) //这个判断非常重要，没有的话T死你 { add(w[son[x]],v,1); add(w[y]+1,-v,1); } } int main() { //freopen("in.txt","r",stdin); int T,u,v,c,m,no=0; char cmd[10]; read(T); while(T--) { memset(head,-1,sizeof(head)); memset(esum,0,sizeof(esum)); memset(psum,0,sizeof(psum)); tol=cnt=0; read(n);read(m); for(int i=1;i<n;i++) { read(edge[i].u);read(edge[i].v); addedge(edge[i].u,edge[i].v); addedge(edge[i].v,edge[i].u); } dfs1(1,1,1); dfs2(1,1); for(int i=1;i<n;i++) if(dep[edge[i].u]<dep[edge[i].v]) swap(edge[i].u,edge[i].v); while(m--) { scanf("%s",cmd); read(u);read(v);read(c); if(cmd[3]=='1') p_Change(u,v,c); if(cmd[3]=='2') e_Change(u,v,c); } printf("Case #%d: ",++no); for(int i=1;i<=n;i++) {if(i>=2) printf(" ");printf("%d",sum(w[i],0));} printf(" "); for(int i=1;i<n;i++) {if(i>=2) printf(" ");printf("%d",sum(w[edge[i].u],1));} printf(" "); } }
| 11824525 | 2014-10-08 17:34:00 | Accepted | 5044 | 3718MS | 11576K | 3384 B | C++ | Physcal |