PART1（算法思想简介）
1.实现、dalao分析：
2.时间复杂度：
3.适用情况、特别优势、需要注意的点：
4.函数、变量名的解释+英文：
PART2（算法各种类型 并 附上代码）
题目 题目 对inId != outId 的dfs了解得很清楚了，只是这样看来只能实现题目要求得这一种询问，未免有点简单
/** 题意： 有一棵点数为 N 的树，以点 1 为根，且树点有边权。然后有 M 个 操作分为三种： 操作 1 ：把某个节点 x 的点权增加 a 。 操作 2 ：把某个节点 x 为根的子树中所有点的点权都增加 a 。 操作 3 ：询问某个节点 x 到根的路径中所有点的点权和。 **/ #include <cstdio> #include <climits> #include <algorithm> using namespace std; int const maxN_ = 100100; typedef long long valueType; struct EDGE { int v; int next; } e[maxN_ << 1]; int p[maxN_]; int eid; valueType valueg[maxN_];//结点i的权重 inline void Insert(int u, int v) { e[eid].v = v; e[eid].next = p[u]; p[u] = eid++; e[eid].v = u; e[eid].next = p[v]; p[v] = eid++; } int inId[maxN_], outId[maxN_]; int inOut[maxN_ << 1];//是否在队列里面的标记，在表示1,出来了负值为-1，不知道初值是-1还是0 int oldId[maxN_ << 1];//oldId[新ID]=它以前的ID int timeCnt;//DFS的时间戳 //二版DFS序，inId != outId(在一版中是相同的) void DFS(int x, int fa) { oldId[timeCnt] = x; inOut[timeCnt] = 1; inId[x] = timeCnt++; for (int next = p[x]; next; next = e[next].next) { int son = e[next].v; if (son != fa) DFS(son, x); } oldId[timeCnt] = x; inOut[timeCnt] = -1; outId[x] = timeCnt++; } int N; valueType fg[maxN_ << 3];//所求子树的答案（不包括本身） valueType lazyg[maxN_ << 3]; int sizeg[maxN_ << 3]; // The count of the positive number in the range（不包括本身） inline int lson(int x) { return x << 1; } inline int rson(int x) { return lson(x) | 1; } inline void PushUp(int id) { fg[id] = fg[lson(id)] + fg[rson(id)]; sizeg[id] = sizeg[lson(id)] + sizeg[rson(id)]; } inline void PushDown(int id) { if (0LL == lazyg[id]) return; valueType &x = lazyg[id];//方便写的快捷写法 int son = lson(id);//但是这种就不能用&了，要注意 fg[son] += sizeg[son] * x; lazyg[son] += x; son = rson(id); fg[son] += sizeg[son] * x; lazyg[son] += x; x = 0LL; } ///建树：这个建树很有意思，一个点对应的in的时间戳和out对应的时间戳中间包含了它子树的in/out的时间戳 void Build(int id, int l, int r) { lazyg[id] = 0LL; if (l == r) { fg[id] = inOut[l] * valueg[oldId[l]];//inOut[in对应的时间戳]是1,反之是-1 sizeg[id] = inOut[l]; return; } int mid = (l + r) >> 1; Build(lson(id), l, mid); Build(rson(id), mid + 1, r); PushUp(id); } //修改操作 void Modify(int id, int l, int r, int x, int y, valueType val) {//和寻常线段树没有任何区别，区别肯定在引用函数前 if (x <= l && r <= y) { fg[id] += sizeg[id] * val; lazyg[id] += val; return; } PushDown(id); int mid = (l + r) >> 1; if (x <= mid) Modify(lson(id), l, mid, x, y, val); if (mid < y) Modify(rson(id), mid + 1, r, x, y, val); PushUp(id); } inline void Modify(int x, valueType val) {//inId != OutId，所以都要增加 Modify(1, 1, N << 1, inId[x], inId[x], val); Modify(1, 1, N << 1, outId[x], outId[x], val);//size是负 } inline void modifySubtree(int x, valueType val) { Modify(1, 1, N << 1, inId[x], outId[x], val); } //线段树询问操作 valueType Query(int id, int l, int r, int x, int y) {//和寻常线段树没有任何区别，区别肯定在引用函数前 if (x <= l && r <= y) { return fg[id]; } PushDown(id); valueType res = 0LL; int mid = (l + r) >> 1; if (x <= mid) res += Query(lson(id), l, mid, x, y); if (mid < y) res += Query(rson(id), mid + 1, r, x, y); return res; } //查询该根（newId == 1）到该点的值 ///中序访问这个点之前访问到的分叉（不在根节点到它上的都由in/out相互抵消了） inline valueType Query(int x) { return Query(1, 1, N << 1, 1, inId[x]); } inline void InitEdge(int n) { eid = 1;//eid不应该赋值成0吗？不过在这题中似乎不重要； timeCnt = 1;//timeCnt比用过的多了1 fill(p, p + n + 1, 0);//fill函数好好学 } int M; bool In() { if (EOF == scanf("%d%d", &N, &M)) return false; InitEdge(N); for (int i = 1; i <= N; ++i) scanf("%lld", valueg + i); int u, v; for (int i = 1; i < N; ++i) { scanf("%d%d", &u, &v); Insert(u, v); } DFS(1, 0); Build(1, 1, N << 1); return true; } void proc() { int cmd, x; valueType a; while (M--) { scanf("%d%d", &cmd, &x); switch (cmd) { case 1: scanf("%lld", &a); Modify(x, a); break; case 2: scanf("%lld", &a); modifySubtree(x, a); break; case 3: printf("%lld ", Query(x)); break; } } } int main() { while (In()) proc(); return 0; }
PART3（算法的延伸应用、深度的理解、相关的有趣题目）