题目链接

题解

点权的 树上差分

代码

#include 
//----
#define  LITERAL_  static constexpr
#define  GET_( _t, _i)  ::std::get< _i>( _t)
#define  PAR_( _type, _name)  const _type & _name
#define  IS_IN_RANGE_( _c, _l, _r)  ( ( (_c) >= (_l)) && ( (_c) <= (_r)))
#define  FOR_( _i, _l, _r, _s)  for( int _i = _l; _i <= _r; _i += _s)
#define  FOR_RE_( _i, _l, _r, _s)  for( int _i = _l; _i >= _r; _i -= _s)
//--
#ifdef  SUPIMO_DEBUG_
  #define DEBUG_( ...)  __Debug( __VA_ARGS__, __LINE__)
#else
  #define DEBUG_( ...)  ( void)0
#endif
//--
using namespace ::std;
using Ll_ = long long;
//--
bool __Debug_is_first = true;
template< class _Last>
void __Debug( _Last _last){
    if( __Debug_is_first){
        cout << "(Debug) ";
        __Debug_is_first = false;
    }
    cout << " [Line: " << _last << "]" << endl;
    __Debug_is_first = true;
}
template< class _Head, class ... _Other>
void __Debug( _Head _head, _Other ... _other ){
    if( __Debug_is_first){
        cout << "(Debug) ";
        __Debug_is_first = false;
    }
    cout << _head << ", ";
    __Debug( _other ...);
}
//----
LITERAL_ int N_ = int( 5e4) + 5;
LITERAL_ int Root_ = 1;
int N, M; //< (点数) (操作)
int Head[ N_], Ver[ N_ * 2], Nex[ N_ * 2], Edges;
int Log[ N_]; //< Log[ a] = b;  2^b <= a, 最大的b
int Depth[ N_], Fa[ N_][ 21];
int Diff[ N_]; //< 树上差分, 起点为叶节点, 即Diff[ i] = A[ i] - ( A[ son(i)]之和)
int A[ N_];
//--
void Init_graph(){
    Edges = 0;
    memset( Head, -1, sizeof( Head));
}
void Add_edge( PAR_( int, _a), PAR_( int , _b)){
    Ver[ Edges] = _b;
    Nex[ Edges] = Head[ _a];
    Head[ _a] = Edges;
    ++ Edges;
}
void Dfs_lca( PAR_( int, _cur), PAR_( int, _fa)){
    for( int nex, i = Head[ _cur]; ~i; i = Nex[ i]){
        nex = Ver[ i];
        if( nex != _fa){
            Depth[ nex] = Depth[ _cur] + 1;
            //--
            Fa[ nex][ 0] = _cur;
            FOR_( step, 1, Log[ Depth[ nex]], 1){
                Fa[ nex][ step] = Fa[ Fa[ nex][ step - 1]][ step - 1];
//                DEBUG_( nex, step, Fa[ nex][ step]);
            }
            //--
            Dfs_lca( nex, _cur);
        }
    }
}
void Build_lca(){
    { //* build `Log`
        FOR_( i, 1, N, 1){
            if( 1 == i){
                Log[ 1] = 0;
            }
            else{
                if( ( 1 << ( Log[ i - 1] + 1)) == i){
                    Log[ i] = Log[ i - 1] + 1;
                }
                else{
                    Log[ i] = Log[ i - 1];
                }
            }
        }
    }
    //--
    Depth[ Root_] = 0;
    Dfs_lca( Root_, -1);
}
int Lca( PAR_( int, _a), PAR_( int, _b)){
    int low = _a, hig = _b;
    if( Depth[ low] < Depth[ hig]){
        swap( low, hig);
    }
    while( Depth[ low] != Depth[ hig]){
        low = Fa[ low][ Log[ Depth[ low] - Depth[ hig]]];
    }
    if( low == hig){ //< 如果不判断, 假如low=Root, 则下面代码中的Log[ 0]是个未定义行为
        return low;
    }
    FOR_RE_( i, Log[ Depth[ low]], 0, 1){ //< not `Log[ low]`
        if( Fa[ low][ i] != Fa[ hig][ i]){
            low = Fa[ low][ i];
            hig = Fa[ hig][ i];
        }
    }
    assert( Fa[ low][ 0] == Fa[ hig][ 0]);
    return Fa[ low][ 0];
}
void Dfs_build_diff( PAR_( int, _cur), PAR_( int, _fa)){
    Diff[ _cur] = A[ _cur];
    for( int nex, i = Head[ _cur]; ~i; i = Nex[ i]){
        nex = Ver[ i];
        if( nex != _fa){
            Diff[ _cur] -= A[ nex];
            //--
            Dfs_build_diff( nex, _cur);
        }
    }
}
void Build_diff(){
//    memset( Diff, 0, sizeof( Diff)); //< 用这个也可以.
    Dfs_build_diff( Root_, -1);
}
void Dfs_restore_diff( PAR_( int, _cur), PAR_( int, _fa)){
    A[ _cur] = Diff[ _cur];
    for( int nex, i = Head[ _cur]; ~i; i = Nex[ i]){
        nex = Ver[ i];
        if( nex != _fa){
            Dfs_restore_diff( nex, _cur);
            A[ _cur] += A[ nex];
        }
    }
}
void Restore_diff(){
    Dfs_restore_diff( Root_, -1);
}
void __Solve(){
    Init_graph();
    scanf("%d%d", &N, &M);
    FOR_( i, 1, N-1, 1){
        int a, b;
        scanf("%d%d", &a, &b);
        Add_edge( a, b);
        Add_edge( b, a);
    }
    Build_lca();
    Build_diff();
    FOR_( i, 1, M, 1){
        int a, b;
        scanf("%d%d", &a, &b);
        int lca = Lca( a, b);
        int fa_lca = ( lca == Root_ ? -1 : Fa[ lca][ 0]);
        Diff[ a] += 1;
        Diff[ b] += 1;
        Diff[ lca] -= 1;
        if( fa_lca != -1){
            Diff[ fa_lca] -= 1;
        }
    }
    Restore_diff();
    int ans = 0;
    FOR_( i, 1, N, 1){
        ans = max( ans, A[ i]);
    }
    cout << ans  << endl;
}
//--
int main(){
    //--
    int tests = 1;
    // scanf("%d", &tests);
    for( int i = 0; i < tests; ++i){
        __Solve();
    }
    return 0;
}

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
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182