(luogu3038)牧草种植(USACO11DEC)

发表于 | 分类于 ， ，

题意描述:

给出一棵n个结点的树, 有m个操作, 操作为将一条路径上的边权加一或询问某条边的边权

解法:

从题意上来看这是一道树上差分的题, 但是如果每次查询都进行一遍dfs将会导致TLE

这时就需要使用dfs序

用树状数组存储dfs序, 然后查询就从O(n)变为O(logn)

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cctype>
using namespace std;
const int Mn(100050);
int qrd()	//快读
{
    int x(0); char c(getchar());
    while(!isdigit(c))  c=getchar();
    while(isdigit(c))
    { x=x*10+c-'0'; c=getchar(); }
    return x;
}
int n;
struct edge	//边表
{
    int e,nt;
}ed[Mn*2];
int vt[Mn],ect(0),d[Mn],dx[Mn],dc(0),cd[Mn],sz[Mn];
/* d:深度, dx:差分数组, dc:时间戳, cd:最初访问时间, sz:子树大小 */
void adde(int s,int e)
{
    ed[++ect].e=e; ed[ect].nt=vt[s];
    vt[s]=ect;
}
inline int lb(int x)	//lowbit(树状数组)
{ return x&-x; }
/* 倍增LCA */
int p[Mn][25];
void dfs(int x)
{
    cd[x] = ++dc;
    sz[x] = 1;
    for(int i(1);i<25;++i)
    {
        p[x][i] = p[p[x][i-1]][i-1];
        if(!p[x][i])    break;
    }
    for(int e(vt[x]);e;e=ed[e].nt)
    {
        if(!d[ed[e].e])
        {
            d[ed[e].e]=d[x]+1;
            p[ed[e].e][0]=x;
            dfs(ed[e].e);
            sz[x] += sz[ed[e].e];
        }
    }
}
int lca(int u,int v)
{
    if(d[u]<d[v])
    { u^=v^=u^=v; }
    int dh(d[u]-d[v]);
    for(int i(0);(1<<i)<=dh;++i)
        if(dh&(1<<i))   u=p[u][i];
    if(u==v)    return u;
    for(int i(24);i>=0;--i)
        if(p[u][i]!=p[v][i])
            u=p[u][i], v=p[v][i];
    return p[u][0];
}
void mdf(int p,int a)	//树状数组修改
{
    while(p<=n)
    {
        dx[p] += a;
        p += lb(p);
    }
}
int qry(int p)	//树状数组查询
{
    int ret(0);
    while(p)
    {
        ret += dx[p];
        p -= lb(p);
    }
    return ret;
}
int main()
{
    int q;
    cin >> n >> q;
    for(int i(1);i<n;++i)
    {
        int x(qrd()),y(qrd());
        adde(x,y), adde(y,x);
    }
    p[1][0]=0, d[1]=1;
    dfs(1);
    while(q--)
    {
        char o; cin >> o;
        int x(qrd()),y(qrd());
        if(o=='P')	//修改
        {
            mdf(cd[x],1), mdf(cd[y],1);
            mdf(cd[lca(x,y)],-2);
        }
        if(o=='Q')	//查询
        {
            int qn(d[x]>d[y] ? x : y);
            printf("%d\n",(qry(cd[qn]+sz[qn]-1)-qry(cd[qn]-1)));
        }
    }
    return 0;
}