首页 > 代码库 > HDU Tree LCA 2014 ACM/ICPC Asia Regional Shanghai Online
HDU Tree LCA 2014 ACM/ICPC Asia Regional Shanghai Online
题意:
给定n个点的树,m个操作
树有点权和边权
下面n-1行给出树边
下面m行操作 :
● ADD1 u v k: for nodes on the path from u to v, the value of these nodes increase by k.
● ADD2 u v k: for edges on the path from u to v, the value of these edges increase by k.
跑个LCA,然后sum0[i]表示i 的点权,lazy0[i]表示 从[i,root] 这条路径上增加的值。
类似于前缀和的思想,最后dfs求个前缀和。
G++栈浅 && 开栈外挂无效,么么哒。。
#pragma comment(linker, "/STACK:1024000000,1024000000") #include <cstdio> #include <cstring> #include <cmath> #include <queue> #include <iostream> #include <algorithm> using namespace std; typedef __int64 ll; inline void rd(int &n){ n = 0; char c = getchar(); while(c < '0' || c > '9') c = getchar(); while(c >= '0' && c <= '9') n *= 10, n += (c - '0'),c = getchar(); } inline void rd64(ll &n){ ll x = 0, tmp = 1; char c = getchar(); while((c < '0' || c > '9') && c != '-' && c != EOF) c = getchar(); if(c == '-') c = getchar(), tmp = -1; while(c >= '0' && c <= '9') x *= 10, x += (c - '0'),c = getchar(); n = x*tmp; } int data[30]; inline void pt(ll n){ if(n < 0) putchar('-'), n = -n; int len = 0; while(n) data[len++] = n%10, n /= 10; if(!len) data[len++] = 0; while(len--) putchar(data[len]+48); } #define N 100005 struct Edge{ int to, nex; }edge[2*N]; int head[N],edgenum,fa[N][20],dep[N]; //fa[i][x] 是i的第2^x个父亲(如果超过范围就是根) void add(int u,int v){ Edge E={v,head[u]}; edge[edgenum] = E; head[u]=edgenum++; } void bfs(int root){ queue<int> q; fa[root][0]=root;dep[root]=0; q.push(root); while(!q.empty()){ int u=q.front();q.pop(); for(int i=1;i<20;i++)fa[u][i]=fa[fa[u][i-1]][i-1]; for(int i=head[u]; ~i;i=edge[i].nex){ int v=edge[i].to;if(v==fa[u][0])continue; dep[v]=dep[u]+1; fa[v][0]=u; q.push(v); } } } int Lca(int x,int y){ if(dep[x]<dep[y])swap(x,y); for(int i=0;i<20;i++)if((dep[x]-dep[y])&(1<<i))x=fa[x][i]; if(x==y)return x; for(int i=19;i>=0;i--)if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i]; return fa[x][0]; } void init(){memset(head, -1, sizeof head); edgenum = 0;} int n, que; ll sum0[N], lazy0[N], sum1[N], lazy1[N]; void dfs(int u, int Father){ sum0[u] += lazy0[u]; sum1[u] += lazy1[u]; for(int i = head[u]; ~i; i = edge[i].nex) { int v = edge[i].to; if( v == Father ) continue; dfs(v, u); sum0[u] += lazy0[v]; sum1[u] += lazy1[v]; lazy0[u] += lazy0[v]; lazy1[u] += lazy1[v]; } } void input() { memset(sum0, 0, sizeof sum0); memset(sum1, 0, sizeof sum1); memset(lazy0, 0, sizeof lazy0); memset(lazy1, 0, sizeof lazy1); rd(n); rd(que); init(); for(int i = 1; i < n; i++) { int u, v; rd(u); rd(v); add(u, v); add(v, u); } bfs(1); } int main() { int T, Cas = 1; rd(T); while (T -- ) { input(); printf("Case #%d:\n", Cas++); char op[6]; int l, r; ll val; while(que--){ scanf("%s", op); rd(l); rd(r); rd64(val); if(dep[l] < dep[r]) swap(l, r); //让l在下面 if(op[3] == '1') { int LCA = Lca(l, r); if(LCA == r) { lazy0[l] += val; //从[l, 1]上增加val lazy0[r] -= val; sum0[r] += val; } else { lazy0[l] += val; lazy0[r] += val; lazy0[LCA] -= val*2LL; sum0[LCA] += val; } } else { int LCA = Lca(l, r); if(LCA == r) { lazy1[l] += val; //从[l, 1]上增加val lazy1[r] -= val; } else { lazy1[l] += val; lazy1[r] += val; lazy1[LCA] -= val*2LL; } } } dfs(1, 1); for(int i = 1; i <= n; i++) { pt(sum0[i]); putchar(i==n?'\n':' '); } int fir = 0; for(int i = 0; i < edgenum; i+=2) { int u = edge[i].to, v = edge[i^1].to; if(dep[u] < dep[v]) u = v; if(fir++)putchar(' '); pt(sum1[u]); } puts(""); } return 0; } /* 99 9 4 1 2 2 3 3 5 5 6 5 7 2 4 4 8 4 9 ADD1 1 9 10 ADD1 1 7 5 ADD1 6 9 3 ADD1 8 7 100 5 4 1 2 2 3 2 4 2 5 ADD1 1 4 1 ADD1 5 3 1 ADD2 5 2 2 ADD2 2 4 1 */
HDU Tree LCA 2014 ACM/ICPC Asia Regional Shanghai Online
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。