题目大意: 有一棵树根为 1, 刚开始每条边的权值为 1, 现在有 m + n - 1 个操作, A :x y , 将 x 和 y 相连的边权值变为 1, W:x, 询问 x 到 1 路径上的权值和.
思路 : 方法一: 用 dfs 序建立树状数组, 每个点入栈位置的值为 1, 出栈为 - 1, 询问的值就是 sum(l [ x] ), 修改就将出栈, 入栈的点全部变成 1, 巧妙的地方在于
利用 dfs 序求前缀和会把不是在这条链上的边全部抵消掉.
方法二: 用 dfs 序建立线段数, 线段数里每个点表示该点到 1 的权值和, 修改一条边相当于把该边下边的子树的值全部减 1, 相当于区间修改.
- #include<bits/stdc++.h>
- #define LL long long
- #define fi first
- #define se second
- #define mk make_pair
- #define pii pair<int,int>
- using namespace std;
- const int N=5e5+7;
- const int M=1e4+7;
- const int inf=0x3f3f3f3f;
- const LL INF=0x3f3f3f3f3f3f3f3f;
- const int mod=1e9 + 7;
- int n, m, tot, st[N], l[N], r[N];
- struct BIT {
- int a[N];
- void modify(int pos, int v) {
- for(int i = pos; i <= tot; i += i & -i)
- a[i] += v;
- }
- int sum(int pos) {
- int ans = 0;
- for(int i = pos; i; i -= i & -i)
- ans += a[i];
- return ans;
- }
- }bit;
- vector<int> edge[N];
- void dfs(int u) {
- l[u] = ++tot;
- for(int i = 0; i <edge[u].size(); i++) {
- int v = edge[u][i];
- dfs(v);
- }
- r[u] = ++tot;
- }
- int main() {
- scanf("%d", &n);
- for(int i = 1; i < n; i++) {
- int u, v; scanf("%d%d", &u, &v);
- if(u> v) swap(u, v);
- edge[u].push_back(v);
- }
- dfs(1);
- for(int i = 1; i <= n; i++) {
- bit.modify(l[i], 1);
- bit.modify(r[i], -1);
- }
- scanf("%d", &m);
- m += n - 1;
- while(m--) {
- char s[5]; scanf("%s", s);
- if(s[0] == 'A') {
- int u, v; scanf("%d%d", &u, &v);
- if(u> v) swap(u, v);
- bit.modify(l[v], -1);
- bit.modify(r[v], 1);
- } else {
- int x; scanf("%d", &x);
- printf("%d\n", bit.sum(l[x]) - 1);
- }
- }
- return 0;
- }
- /*
- */
- bzoj 1103
来源: http://www.bubuko.com/infodetail-2591482.html