首页 > 代码库 > hdu 3966 树链剖分第3遍
hdu 3966 树链剖分第3遍
真心不好意思说话,写的越多,各种问题就暴漏出来了,这次更离谱,什么错误都有。。。不过还是过了。也明白了代码以后要写规范性,不能想当然。。。
#include<cstdio> #include<cstring> #pragma comment(linker, "/STACK:1024000000,1024000000") #include<iostream> #include<algorithm> using namespace std; const int M = 50100; int son[M],top[M],father[M],dep[M],ti[M],siz[M]; int idx,tp,n; struct { int head; }H[M]; struct { int v,next; }E[M]; void dfs_1(int u,int fa){ son[u] = 0;siz[u] = 1;father[u] = fa;dep[u] = dep[fa] + 1; for(int i=H[u].head;i!=-1;i=E[i].next){ int v = E[i].v; if(v == fa)continue; dfs_1(v,u); siz[u] += siz[v]; if(siz[son[u]] < siz[v])son[u] = v; } } void dfs_2(int u,int fa){ top[u] = fa; ti[u] = idx++; if(son[u]) dfs_2(son[u],fa); for(int i=H[u].head;i!=-1;i=E[i].next){ int v = E[i].v; if(v == father[u]|| v == son[u])continue; dfs_2(v,v); } } int lobit(int x){ return x&(-x); } int num[M*2]; void update(int x ,int d){ while( x <= n){ num[x] += d; x += lobit(x); } } void change(int u,int v,int w){ int f1 = top[u]; int f2 = top[v]; while(f1 != f2){ if(dep[f1] <dep[f2]){ swap(f1,f2); swap(u,v); } update(ti[f1],w); update(ti[u]+1,-w); u = father[f1];f1 = top[u]; } if(dep[u] > dep[v])swap(u,v); update(ti[u],w); update(ti[v]+1,-w); } int sum(int x){ int ans = 0; while(x>0){ ans += num[x]; x -= lobit(x); } return ans; } void add(int u,int v){ E[tp].v = v; E[tp].next = H[u].head; H[u].head = tp++; } void init(){ memset(E,-1,sizeof(E)); memset(H,-1,sizeof(H)); memset(num,0,sizeof(num)); tp = 0; idx = 1; } int findp(int x){ return sum(ti[x]); } int a[M]; int main(){ // freopen("input.txt","r",stdin); int m,p,u,v,w; while(scanf("%d%d%d",&n,&m,&p)==3){ init(); for(int i=1;i<=n;i++){ scanf("%d",&a[i]); } while(m -- ){ scanf("%d%d",&u,&v); add(u,v);add(v,u); } dfs_1(1,1); dfs_2(1,1); for(int i=1;i<=n;i++){ update(ti[i],a[i]); update(ti[i]+1,-a[i]); } char op[100]; while (p--){ scanf("%s%d",op,&u); if(op[0] == 'Q'){ printf("%d\n",sum(ti[u])); }else { scanf("%d%d",&v,&w); if(op[0] == 'D')w = -w; change(u,v,w); } } } }
hdu 3966 树链剖分第3遍
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。