题目
点这里看题目。
分析
如果你熟悉问题的结构的话，你会发现题目要求的相当于是树上带权重心。
关于这一点的说明：
考虑现在将任意一点 (u) 提作根，并设 (sd_u) 为 (u) 子树内的 (d) 之和。
那么考虑 (u) 的一个儿子 (v) ，如果现在将根从 (u) 颠倒到 (v) ，那么答案会发生什么变化？
不妨设 ((u,v)) 的权为 (l) 。如果换到了 (v) 会更优，则有：
[egin{aligned} sd_v imes l-(sd_u-sd_v) imes l&<0\ 2sd_v&>sd_u end{aligned} ]当不存在一个儿子 (v) 满足这个条件的时候，可以发现 (u) 就是我们要求的答案。而不难发现最终的 (u) 一定满足树上带权重心的性质。
那么我们只需要干两件事情：
- 可以快速找出树上带权重心是哪一个。
- 可以快速查询 (u) 确定时候的 (sum_v d_v imes dist(u,v)) 。
后一个很好做，我们可以直接点分树维护一下，不是问题。
而前一个问题则比较棘手，直接模拟会退化到 (O(n^2)) ，会 T 的......
为了优化这个过程，我们不难想到最开始选择根，可以直接选树的大小重心；找到了目标子树之后，我们也可以将目标子树的大小重心提作新的根。这样每迭代一次，树的大小必然折半，可以保证迭代次数。
考虑同样用点分树维护这个过程，我们实际上只需要维护 " 换根 " 的过程。设当前点为 (u) ，目标为 (v) 的子树，而 (v) 的子树的重心是 (c) ，那么将 (c) 提作新根的时候，就相当于将 (v) 在 (c) 范围下的子树加上了 (u) 除 (v) 以外的内容。注意到之后我们一定不会回到 (u) ，因此可以直接在点分树上，将 (c) 及其祖先分治块的大小全部加上外部的权。
u 会影响 c 作根时 v 所在的子树
这样做的时间即是 (O(nlog_2^2n)) 的。
在本题中会有一个 20 的常数。
代码
#include <cstdio>
#define rep( i, a, b ) for( int i = (a) ; i <= (b) ; i ++ )
#define per( i, a, b ) for( int i = (a) ; i >= (b) ; i -- )
typedef long long LL;
const int MAXN = 1e5 + 5, MAXLOG = 17;
template<typename _T>
void read( _T &x )
{
x = 0; char s = getchar(); int f = 1;
while( s < '0' || '9' < s ) { f = 1; if( s == '-' ) f = -1; s = getchar(); }
while( '0' <= s && s <= '9' ) { x = ( x << 3 ) + ( x << 1 ) + ( s - '0' ), s = getchar(); }
x *= f;
}
template<typename _T>
void write( _T x )
{
if( x < 0 ) putchar( '-' ), x = - x;
if( 9 < x ) write( x / 10 );
putchar( x % 10 + '0' );
}
template<typename _T>
_T MIN( const _T a, const _T b )
{
return a < b ? a : b;
}
template<typename _T>
_T MAX( const _T a, const _T b )
{
return a > b ? a : b;
}
struct MyGraph
{
struct Edge
{
int to, nxt, w;
}Graph[MAXN << 1];
int head[MAXN], cnt;
Edge& operator [] ( const int idx ) { return Graph[idx]; }
void AddE( const int from, const int to, const int W = 0 )
{ AddEdge( from, to, W ), AddEdge( to, from, W ); }
void AddEdge( const int from, const int to, const int W = 0 )
{
Graph[++ cnt].to = to, Graph[cnt].nxt = head[from];
Graph[cnt].w = W, head[from] = cnt;
}
}T, nwT;
int wei[MAXN][MAXLOG], fath[MAXN][MAXLOG];
LL dSu[MAXN], wSu[MAXN], faWSu[MAXN];
int DFN[MAXN], dep[MAXN], siz[MAXN], inter[MAXN];
int N, Q, rt;
bool vis[MAXN];
int GetCen( const int u, const int fa, const int all )
{
int mx = 0, ret = 0; siz[u] = 1;
for( int i = T.head[u], v ; i ; i = T[i].nxt )
if( ! vis[v = T[i].to] && v ^ fa )
{
ret |= GetCen( v, u, all );
siz[u] += siz[v], mx = MAX( mx, siz[v] );
}
if( ( MAX( mx, all - siz[u] ) << 1 ) <= all ) ret = u;
return ret;
}
void DFS( const int u, const int fa, const int fr, const int dis, const int d )
{
wei[u][d] = dis, fath[u][d] = fr;
for( int i = T.head[u], v ; i ; i = T[i].nxt )
if( ( v = T[i].to ) ^ fa && ! vis[v] )
DFS( v, u, fr, dis + T[i].w, d );
}
void Divide( const int u, const int all, const int d )
{
dep[u] = d, DFS( u, 0, u, 0, d ), vis[u] = true;
for( int i = T.head[u], v, t, nxt ; i ; i = T[i].nxt )
if( ! vis[v = T[i].to] )
{
t = siz[v] > siz[u] ? all - siz[u] : siz[v];
nxt = GetCen( v, u, t ), inter[nxt] = v;
nwT.AddEdge( u, nxt ), Divide( nxt, t, d + 1 );
}
}
void Update( const int u, const int delt )
{
dSu[u] += delt;
for( int i = dep[u] - 1, v, w ; ~ i ; i -- )
{
v = fath[u][i], w = fath[u][i + 1];
dSu[v] += delt, wSu[v] += 1ll * wei[u][i] * delt;
faWSu[w] += 1ll * wei[u][i] * delt;
}
}
LL GetSum( const int u )
{
LL ret = wSu[u];
per( i, dep[u] - 1, 0 )
ret += wSu[fath[u][i]] - faWSu[fath[u][i + 1]]
+ wei[u][i] * ( dSu[fath[u][i]] - dSu[fath[u][i + 1]] );
return ret;
}
void Change( const int u, const LL delt ) { rep( k, 0, dep[u] ) dSu[fath[u][k]] += delt; }
int GetBest( const int u )
{
int ret = u; LL delt;
for( int i = nwT.head[u], v ; i ; i = nwT[i].nxt )
if( 2 * dSu[v = nwT[i].to] > dSu[u] )
{
delt = dSu[u] - dSu[v];
Change( inter[v], delt );
ret = GetBest( v );
Change( inter[v], - delt );
}
return ret;
}
int main()
{
read( N ), read( Q );
rep( i, 1, N - 1 ) { int a, b, c;
read( a ), read( b ), read( c );
T.AddE( a, b, c );
}
Divide( rt = GetCen( 1, 0, N ), N, 0 );
for( int x, e ; Q -- ; )
{
read( x ), read( e );
Update( x, e );
x = GetBest( rt );
write( GetSum( x ) ), putchar( '
' );
}
return 0;
}