HDU Tree LCA 2014 ACM/ICPC Asia Regional Shanghai Online
來(lái)源：程序員人生 發(fā)布時(shí)間：2014-10-02 08:00:00 閱讀次數(shù)：2985次
題意：
給定n個(gè)點(diǎn)的樹(shù)，m個(gè)操作
樹(shù)有點(diǎn)權(quán)和邊權(quán)
下面n-1行給出樹(shù)邊
下面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.
跑個(gè)LCA，然后sum0[i]表示i 的點(diǎn)權(quán)，lazy0[i]表示 從[i,root] 這條路徑上增加的值。
類似于前綴和的思想，最后dfs求個(gè)前綴和。
G++棧淺 && 開(kāi)棧外掛無(wú)效，么么噠。。
#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個(gè)父親（如果超過(guò)范圍就是根）
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:
", 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?'
':' ');
}
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
*/
生活不易，碼農(nóng)辛苦
如果您覺(jué)得本網(wǎng)站對(duì)您的學(xué)習(xí)有所幫助,可以手機(jī)掃描二維碼進(jìn)行捐贈(zèng)
