hdu5044 Tree 树链拆分。点细分。刚，非递归版本
//#pragma warning (disable: 4786)
//#pragma comment (linker, "/STACK:16777216")
//#pragma comment(linker, "/STACK:60400000,60400000") //HEAD
#include <cstdio>
#include <ctime>
#include <cstdlib>
#include <cstring>
#include <queue>
#include <string>
#include <set>
#include <stack>
#include <map>
#include <cmath>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
//LOOP
#define FE(i, a, b) for(int i = (a); i <= (b); ++i)
#define FD(i, b, a) for(int i = (b); i>= (a); --i)
#define REP(i, N) for(int i = 0; i < (N); ++i)
#define CLR(A,value) memset(A,value,sizeof(A))
#define CPY(a, b) memcpy(a, b, sizeof(a))
#define FC(it, c) for(__typeof((c).begin()) it = (c).begin(); it != (c).end(); it++)
//INPUT
#define RI(n) scanf("%d", &n)
#define RII(n, m) scanf("%d%d", &n, &m)
#define RIII(n, m, k) scanf("%d%d%d", &n, &m, &k)
#define RS(s) scanf("%s", s)
//OUTPUT
#define WI(n) printf("%d\n", n)
#define WS(s) printf("%s\n", s) typedef long long LL;
const int INF = 1000000007;
const double eps = 1e-10; const int MAXN = 100020; int n; int e[MAXN][2];
int idx_e[MAXN];
int ans_e[MAXN]; struct Edge{
int to, next;
};
Edge adj[MAXN * 2];
int head[MAXN], tol;
int hd[MAXN]; int top[MAXN];///top[v]表示v所在重链的顶端定点
int fa[MAXN];///fa[v]表示v的父节点,没有为-1
int deep[MAXN];///deep[v]表示v在树中的深度，根点为1
int num[MAXN];///num[v]表示以v为根的子树的节点数 int son[MAXN];///重儿子，没有为-1
int p[MAXN];///p[v]表示v和其父亲节点的连边在线段树的位置（标号) int point_p[MAXN];
int point_pos; int pos; inline void init()
{
tol = 0;///init_edge
//CLR(head, -1);
for (int i = 0; i <= n + 10; i++) head[i] = -1, son[i] = -1; pos = 0;///init_p
//CLR(son, -1); point_pos = 0;
}
inline void add_edge(int u, int v)
{
adj[tol].to = v;
adj[tol].next = head[u];
head[u] = tol++;
} void dfs1(int u, int pre, int d)///求出fa, deep, num, son
{
deep[u] = d;
fa[u] = pre;
num[u] = 1; for (int r = head[u]; r != -1; r = adj[r].next)
{
int v = adj[r].to;
if (v != pre)
{
dfs1(v, u, d + 1);
num[u] += num[v];
if (son[u] == -1 || num[v] > num[son[u]])
son[u] = v;
}
}
} struct sknode{
int u, pre, d;
sknode(){}
sknode(int u, int pre, int d):u(u), pre(pre), d(d)
{
}
};
int fir[MAXN];
void bfs1()
{
stack<sknode>sk;
for (int i = 0; i <= n + 10; i++) hd[i] = head[i], fir[i] = 0; sk.push(sknode(1, -1, 1));
while (!sk.empty())
{
sknode sku = sk.top();
int u = sku.u, d = sku.d, pre = sku.pre;
int r = hd[u];
if (!fir[u])
{
fir[u] = 1;
deep[u] = d;
fa[u] = pre;
num[u] = 1;
}
if (r == -1)
{
if (pre != -1)
{
num[pre] += num[u];
if (son[pre] == -1 || num[u] > num[son[pre]])
son[pre] = u;
}
sk.pop();
}
else
{
int v = adj[r].to;
if (v != pre)
{
sk.push(sknode(v, u, d +1));
}
hd[u] = adj[r].next;
}
}
} void getpos(int u, int sp)///top, p, fp
{
top[u] = sp;
p[u] = ++pos;
ans_e[ idx_e[u] ] = pos;
point_p[u] = ++point_pos; if (son[u] != -1)
getpos(son[u], sp);
else return ;
for (int r = head[u]; r != -1; r = adj[r].next)
{
int v = adj[r].to;
if (v != son[u] && v != fa[u])
getpos(v, v);
}
}
struct node{
int u, sp;
node(){}
node(int u, int sp):u(u), sp(sp){}
};
void bfs2()
{
stack<node> sk;
for (int i = 0; i <= n + 10; i++) hd[i] = head[i], fir[i] = 0;
sk.push(node(1, 1)); while (!sk.empty())
{
node sku = sk.top();
int u = sku.u, sp = sku.sp;
int r = hd[u];
if (!fir[u])
{
fir[u] = 1;
top[u] = sp;
p[u] = ++pos;
ans_e[ idx_e[u] ] = pos;
point_p[u] = ++point_pos; if (son[u] != -1)
{
sk.push(node(son[u], sp));
}
else
{
sk.pop();
}
continue;
}
if (r == -1)
{
sk.pop();
}
else
{
int v = adj[r].to;
if (v != son[u] && v != fa[u])
{
sk.push(node(v, v));
}
hd[u] = adj[r].next;
}
}
} ///
LL sum[2][MAXN];
inline int lowbit(int x)
{
return x & (-x);
}
inline void add(int i, int x, int op)
{
for (; i <= n + 10; i += lowbit(i))
{
sum[op][i] += x;
}
}
inline LL getsum(int i, int op)
{
LL ret = 0;
for (; i > 0; i -= lowbit(i))
ret += sum[op][i];
return ret;
} inline void update(int u, int v, int val, int op)
{
int fu = top[u];
int fv = top[v]; while (fu != fv)
{
if (deep[fu] < deep[fv])
{
swap(fu, fv);
swap(u, v);
} add(p[fu], val, op);
add(p[u] + 1, -val, op); u = fa[fu]; fu = top[u];
}
if (u == v) return ;
if (deep[u] > deep[v]) swap(u, v); add(p[son[u]], val, op);
add(p[v] + 1, -val, op);
///假设是点剖分的话query(p[u], p[v], 1, pos, 1)
} inline void point_update(int u, int v, int val, int op)
{
int fu = top[u];
int fv = top[v]; while (fu != fv)
{
if (deep[fu] < deep[fv])
{
swap(fu, fv);
swap(u, v);
} //cout << point_p[fu] << ' ' << point_p[u] <<endl; add(point_p[fu], val, op);
add(point_p[u] + 1, -val, op); u = fa[fu]; fu = top[u];
}
if (deep[u] > deep[v]) swap(u, v);
//cout << point_p[u] << ' ' << point_p[v] <<endl; add(point_p[u], val, op);
add(point_p[v] + 1, -val, op);
///假设是点剖分的话query(p[u], p[v], 1, pos, 1)
} char cc;
inline void read(int &ret)
{
ret = 0;
cc = getchar();
while (cc < '0' || cc > '9') cc = getchar();
while (cc >= '0' && cc <= '9')
{
ret = (ret << 3) + (ret << 1) + cc - '0';
cc = getchar();
}
}
inline void out(LL ret)
{
if (ret > 9) out(ret / 10);
putchar(ret % 10 + '0');
} int main ()
{
char op[10];
int T, Q;
int ncase = 1;
int u, v;
int x, y, z;
read(T);
while (T--)
{
init();
//RII(n, Q);
read(n); read(Q);
FE(i, 1, n - 1)
{
read(e[i][0]); read(e[i][1]);
//RII(e[i][0], e[i][1]);
add_edge(e[i][0], e[i][1]);
add_edge(e[i][1], e[i][0]);
}
bfs1();
//puts("***********");
//dfs1(1, -1, 1);
FE(i, 1, n - 1)
{
if (deep[e[i][0]] > deep[e[i][1]])
swap(e[i][0], e[i][1]);
idx_e[e[i][1]] = i;
}
bfs2();
//puts("***********");
//getpos(1, 1); for (int i = 0; i <= n + 10; i++) sum[0][i] = sum[1][i] = 0;
//CLR(sum, 0);///初始化 while (Q--)
{
scanf("%s", op);
read(x); read(y); read(z);
//scanf("%d%d%d", &x, &y, &z);
if (op[3] == '1')
{
//puts("***********"); point_update(x, y, z, 0);
}
else
{
update(x, y, z, 1);
}
} printf("Case #%d:\n", ncase++);
for (int i = 1; i <= n; i++)
{
out(getsum(point_p[i], 0));
//printf("%I64d", getsum(point_p[i], 0));
//printf("%I64d", getsum(point_p[i], 0));
if (i == n) printf("\n");
else printf(" ");
}
if (n == 1) printf("\n");
else
for (int i = 1; i < n; i++)
{
//printf("%I64d", getsum(mp[make_pair(e[i][1], e[i][0])], 1));
out( getsum(ans_e[i], 1) );
//printf("%I64d", getsum(ans_e[i], 1));
if (i == n - 1) printf("\n");
else printf(" ");
}
}
return 0;
}
版权声明：本文博主原创文章，博客，未经同意不得转载。