题目
题意简述
给定两颗树 (A,B)，(A) 中的任一结点 (u) 与 (B) 中的任一结点 (v) 都有一个关系值 (f(u,v))，初始为 (0)。再给出 (q) 个形如 (a1,b1,a2,b2,c) 的操作，表示对于 (A) 中路径 (a1leftrightarrow b1) 上的任一结点 (u) 和 (B) 中路径 (a2leftrightarrow b2) 上的任一结点 (v)，(f(u,v)leftarrow f(u,v)+c)。求操作完成后所有的 (f(u,v))。
数据规模
设 (A) 的结点数 (n)，(B) 的结点数 (m)。
(n,mle10^4;~qle5 imes10^5)。
题解
一道有意思的差分题 owo。
首先将 (A) 和 (B) 分别树链剖分，把结点编号转化为 (DFN) 来考虑问题。
形象地，我们把 (f) 列成一个表格，第 (i) 行第 (j) 列的值表示 (A) 中 (DFN) 为 (i) 的结点 (u) 和 (B) 中 (DFN) 为 (j) 的结点 (v) 的 (f(u,v)) 值。如果操作涉及路径的 (DFN) 值连续，那么就相当于修改这个表格的一个子矩阵，可以差分做到。推广到一般情况，只需要用树剖取出 (A) 中路径所覆盖的若干个 (DFN) 区间和 (B) 中路径覆盖的若干个 (DFN) 区间，暴力地两两配对，修改子矩阵即可。最后前缀和还原表格，就求出每一个 (f(u,v)) 啦～
复杂度 (O(qlog^2n))。
代码
#include <cstdio>
#include <vector>
#include <utility>
#define x1 tmpx1
#define y1 tmpy1
#define x2 tmpx2
#define y2 tmpy2
inline int rint () {
int x = 0, f = 1; char s = getchar ();
for ( ; s < '0' || '9' < s; s = getchar () ) f = s == '-' ? -f : f;
for ( ; '0' <= s && s <= '9'; s = getchar () ) x = x * 10 + ( s ^ '0' );
return x * f;
}
template<typename Tp>
inline void wint ( Tp x ) {
if ( x < 0 ) putchar ( '-' ), x = ~ x + 1;
if ( 9 < x ) wint ( x / 10 );
putchar ( x % 10 ^ '0' );
}
const int MAXN = 1e4;
struct TreeSplit {
int n, fa[MAXN + 5], dep[MAXN + 5], son[MAXN + 5], siz[MAXN + 5];
int indx, top[MAXN + 5], dfn[MAXN + 5], ref[MAXN + 5];
std :: vector<int> graph[MAXN + 5];
inline void read () {
n = rint ();
for ( int i = 1, u, v; i < n; ++ i ) {
u = rint (), v = rint ();
graph[u].push_back ( v ), graph[v].push_back ( u );
}
}
inline void DFS1 ( const int u, const int f ) {
dep[u] = dep[fa[u] = f] + ( siz[u] = 1 );
for ( int v: graph[u] ) if ( v ^ f ) {
DFS1 ( v, u ), siz[u] += siz[v];
if ( siz[son[u]] < siz[v] ) son[u] = v;
}
}
inline void DFS2 ( const int u, const int tp ) {
top[ref[dfn[u] = ++ indx] = u] = tp;
if ( son[u] ) DFS2 ( son[u], tp );
for ( int v: graph[u] ) if ( v ^ fa[u] && v ^ son[u] ) DFS2 ( v, v );
}
inline std :: vector<std :: pair<int, int> > getPath ( int u, int v ) {
static std :: vector<std :: pair<int, int> > ret; ret.clear ();
while ( top[u] ^ top[v] ) {
if ( dep[top[u]] < dep[top[v]] ) u ^= v ^= u ^= v;
ret.push_back ( { dfn[top[u]], dfn[u] } ), u = fa[top[u]];
}
if ( dep[u] < dep[v] ) u ^= v ^= u ^= v;
return ret.push_back ( { dfn[v], dfn[u] } ), ret;
}
} T1, T2;
int sum[MAXN + 5][MAXN + 5];
inline void add ( const int x1, const int y1, const int x2, const int y2, const int k ) {
sum[x1][y1] += k, sum[x1][y2 + 1] -= k, sum[x2 + 1][y1] -= k, sum[x2 + 1][y2 + 1] += k;
}
int main () {
T1.read (), T2.read ();
T1.DFS1 ( 1, 0 ), T1.DFS2 ( 1, 1 );
T2.DFS1 ( 1, 0 ), T2.DFS2 ( 1, 1 );
std :: vector<std :: pair<int, int> > pathA, pathB;
for ( int q = rint (), a, b, u, v, k; q --; ) {
a = rint (), b = rint (), u = rint (), v = rint (), k = rint ();
pathA = T1.getPath ( a, b ), pathB = T2.getPath ( u, v );
for ( auto seca: pathA ) for ( auto secb: pathB ) {
add ( seca.first, secb.first, seca.second, secb.second, k );
}
}
for ( int i = 1; i <= T1.n; ++ i ) {
for ( int j = 1; j <= T2.n; ++ j ) {
sum[i][j] += sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
}
}
long long ans = 0;
for ( int i = 1; i <= T1.n; ++ i ) {
for ( int j = 1; j <= T2.n; ++ j ) {
ans ^= 1ll * T1.ref[i] * T2.ref[j] * sum[i][j];
}
}
wint ( ans ), putchar ( '
' );
return 0;
}