@hdu - 6594@ Double Tree

深藏阁楼爱情的钟 2023-06-01 13:56 9阅读 0赞

*  @description@
 *  @solution@
 *  @accepted code@
 *  @details@

--------------------

## @description@ ##

给定两棵 N 个点的树，以及树上每条边的权值 w(u, v)，每个点的初始点权 val(u)。

有 Q 次操作。每次操作更改一个点的点权，请在每次操作后输出 \\(\\max\_\{1 \\le u < v \\le n\}\\\{T\_1.dis(u,v)+T\_2.dis(u,v)+val(u)+val(v)\\\}\\)。

**Input**  
多组数据。  
每组数据以 N, Q (2≤N≤10^5,1≤Q≤10^5) 开头，含义如上。  
接下来第二行包含 N 个整数 a1, a2, ..., aN (1≤ai≤10^9) 描述每个点的初始点权。  
接下来 N-1 行，每行包含三个整数 u, v, w (1≤u,v≤n,1≤w≤10^9) 描述第一棵树上的边。  
接下来 N-1 行，每行包含三个整数 u, v, w (1≤u,v≤n,1≤w≤10^9) 描述第二棵树上的边。  
接下来 Q 行，每行包含两个整数 u, w(1≤u≤n,1≤w≤10^9) 描述将 u 的点权更改为 w。

**Output**  
对于每组数据，输出 Q 行。每行表示每次更改点权后的答案。

**Sample Input**  
5 3  
1 2 3 4 5  
1 2 1  
1 3 2  
1 4 3  
1 5 4  
1 2 1  
1 3 2  
1 4 3  
1 5 4  
1 100  
1 1  
2 100  
**Sample Output**  
113  
23  
115

## @solution@ ##

考虑没有修改的时候，我们应该怎么做。  
因为是两棵树的两点距离之和，可以考虑类比 WC2018 中通道一题，使用边分治来解决。

具体来说，我们对 T1 进行边分治，每一次处理经过中心边的路径。  
处理出 f\[i\] 表示点 i 离当前中心边的距离，令 w 表示当前中心边的权值，则 T1.dis(u, v) = f\[u\] + f\[v\] + w（这里要求 u, v 处在中心边的两侧）。  
则我们需要最大化的 T1.dis(u, v) + T2.dis(u, v) + val(u) + val(v) = T2.dis(u, v) + (f\[u\] + val(u)) + (f\[v\] + val(v)) + w。

因为 w 是个常数，我们只需要最大化前面那一部分。  
可以考虑建边 u' -> u，边权为 f\[u\] + val(u)，因此将问题转为 T2.dis(u', v') 最大（当然实际操作时并不需要真的建出 u' -> u 这条边）。  
我们有结论：若从点集 S 中选择一个端点、从点集 T 中选择另一个端点使得两个端点距离最远，则这两个端点一定在 S 中距离最远的两个端点、T 中距离最远的两个端点中两两配对产生。  
于是每次加入一个点，维护一下 S 中的直径端点、T 中的直径端点即可。

现考虑修改。我们不妨依照边分治的分治顺序，建出边分树。其中，边分树上的叶结点为原树的点、非叶结点为原树的边（有些类似于 kruskal 重构树），非叶结点连向这个结点表示的中心边的两侧连通块。  
这样，每次加入一个点权时，只需要顺着边分树从上往下走，顺便更新沿途的非叶结点的值（就是上文说的 S 直径，T 直径）就可以快速维护出答案。因为边分治的性质，边分树深度为 O(logn)，于是加入一个点权的复杂度为 O(logn)。

但是可以看到上述过程并不支持删除，但可以撤回。  
所以我们考虑维护出每种点权出现的时间区间，然后使用线段树分治。这样就只剩下在边分树上插入和撤回两种操作了，时间复杂度 O(nlog^2n)。

## @accepted code@ ##

#pragma GCC optimize(2) #include<cstdio> #include<iostream> #include<algorithm> using namespace std; #define fi first #define se second typedef long long ll; typedef pair<int, int> pii; const int MAXN = 200000; int lg[MAXN + 5]; struct Graph{ struct edge{ edge *nxt, *rev; int to, dis; bool tag; }edges[2*MAXN + 5], *adj[MAXN + 5], *ecnt; int dfn[2*MAXN + 5], fir[MAXN + 5], dep[MAXN + 5], dcnt; ll dis[MAXN + 5]; void init(int n) { ecnt = &edges[0]; for(int i=1;i<=n;i++) adj[i] = NULL; dcnt = 0; } void addedge(int u, int v, int w) { // printf("! %d %d %d\n", u, v, w); edge *p = (++ecnt), *q = (++ecnt); p->to = v, p->dis = w, p->tag = false, p->nxt = adj[u], adj[u] = p; q->to = u, q->dis = w, q->tag = false, q->nxt = adj[v], adj[v] = q; p->rev = q, q->rev = p; } void dfs(int x, int f, ll d) { dfn[++dcnt] = x, fir[x] = dcnt, dep[x] = dep[f] + 1, dis[x] = d; for(edge *p=adj[x];p;p=p->nxt) { if( p->to == f ) continue; dfs(p->to, x, d + p->dis); dfn[++dcnt] = x; } } int st[20][MAXN + 5]; void get_st() { for(int i=1;i<=dcnt;i++) st[0][i] = dfn[i]; for(int j=1;j<20;j++) { int t = (1<<(j-1)); for(int i=1;i+t<=dcnt;i++) st[j][i] = (dep[st[j-1][i]] <= dep[st[j-1][i+t]]) ? st[j-1][i] : st[j-1][i+t]; } } void build() {dfs(1, 0, 0), get_st();} int lca(int u, int v) { if( fir[u] > fir[v] ) swap(u, v); int k = lg[fir[v] - fir[u] + 1], l = (1<<k); return (dep[st[k][fir[u]]] <= dep[st[k][fir[v]-l+1]]) ? st[k][fir[u]] : st[k][fir[v]-l+1]; } ll dist(int u, int v) {return dis[u] + dis[v] - 2*dis[lca(u, v)];} }G1, G2, G3; struct query{ int l, r, x, k; query(int _l=0, int _r=0, int _x=0, int _k=0):l(_l), r(_r), x(_x), k(_k) {} }qry[MAXN + 5]; int a[MAXN + 5], b[MAXN + 5]; int N, Q, M, tot = 0; void rebuild(int x, int f) { int lst = -1; for(Graph::edge *p=G1.adj[x];p;p=p->nxt) { if( p->to == f ) continue; rebuild(p->to, x); if( lst == -1 ) { G3.addedge(x, p->to, p->dis); lst = x; } else { int s = (++M); G3.addedge(s, p->to, p->dis); G3.addedge(lst, s, 0); lst = s; } } } bool arr[30][MAXN + 5]; ll dis[30][MAXN + 5]; Graph::edge *e[MAXN + 5]; int ch[2][MAXN + 5], cnt = 0; int siz[MAXN + 5]; void update(Graph::edge *&a, Graph::edge *b, int tot) { if( a == NULL ) a = b; if( b && max(siz[b->to], tot-siz[b->to]) <= max(siz[a->to], tot-siz[a->to]) ) a = b; } Graph::edge *get_mid_edge(int x, int f, int tot) { Graph::edge *ret = NULL; siz[x] = 1; for(Graph::edge *p=G3.adj[x];p;p=p->nxt) { if( p->tag || p->to == f ) continue; update(ret, get_mid_edge(p->to, x, tot), tot); siz[x] += siz[p->to]; update(ret, p, tot); } return ret; } void dfs(int x, int f, bool t, ll d, const int &dep) { arr[dep][x] = t, dis[dep][x] = d; for(Graph::edge *p=G3.adj[x];p;p=p->nxt) { if( p->tag || p->to == f ) continue; dfs(p->to, x, t, d + p->dis, dep); } } int divide(int x, int tot, int dep) { Graph::edge *m = get_mid_edge(x, 0, tot); if( m == NULL ) return -1; int tmp = (++cnt); e[tmp] = m; m->tag = m->rev->tag = true; dfs(m->to, 0, 0, 0, dep), dfs(m->rev->to, 0, 1, 0, dep); ch[0][tmp] = divide(m->to, siz[m->to], dep + 1); ch[1][tmp] = divide(m->rev->to, tot-siz[m->to], dep + 1); return tmp; } void init() { G1.init(2*N), G2.init(2*N), G3.init(2*N); for(int i=2;i<=2*N;i++) lg[i] = lg[i>>1] + 1; cnt = tot = 0; } pair<pii, pii>res[MAXN + 5]; ll nwans = 0; struct modify{ bool type; pii a; int b; modify(bool _t=0, pii _a=make_pair(0,0), int _b=0):type(_t), a(_a), b(_b) {} }stk[32*MAXN + 5]; int tp; void restore(int x) { while( tp > x ) { modify p = stk[tp--]; if( p.type == 0 ) res[p.b].fi = p.a; if( p.type == 1 ) res[p.b].se = p.a; } } ll func(const int &x, const int &y, const int &d, const int &p) { return dis[d][x] + dis[d][y] + e[p]->dis + a[x] + a[y] + G2.dist(x, y); } void insert(int x, int k) { a[x] = k; int p = 1, d = 0; while( p != -1 ) { if( arr[d][x] ) { stk[++tp] = modify(1, res[p].se, p); if( res[p].se.fi ) { ll _p = func(res[p].se.fi, x, d, p), _q = func(res[p].se.se, x, d, p), _r = func(res[p].se.fi, res[p].se.se, d, p); if( _p >= _q && _p >= _r ) res[p].se.se = x; else if( _q >= _p && _q >= _r ) res[p].se.fi = x; else tp--; } else res[p].se = make_pair(x, x); if( res[p].fi.fi ) nwans = max(nwans, max(func(x, res[p].fi.fi, d, p), func(x, res[p].fi.se, d, p))); } else { stk[++tp] = modify(0, res[p].fi, p); if( res[p].fi.fi ) { ll _p = func(res[p].fi.fi, x, d, p), _q = func(res[p].fi.se, x, d, p), _r = func(res[p].fi.fi, res[p].fi.se, d, p); if( _p >= _q && _p >= _r ) res[p].fi.se = x; else if( _q >= _p && _q >= _r ) res[p].fi.fi = x; else tp--; } else res[p].fi = make_pair(x, x); if( res[p].se.fi ) nwans = max(nwans, max(func(x, res[p].se.fi, d, p), func(x, res[p].se.se, d, p))); } p = ch[arr[d][x]][p], d++; } } void solve(int le, int ri, int n) { if( n == 0 ) return ; int tmp = tp; ll tmp2 = nwans; for(int i=n;i>=1;i--) if( qry[i].l <= le && ri <= qry[i].r ) { swap(qry[i], qry[n]); insert(qry[n].x, qry[n].k); n--; } if( le == ri ) { printf("%lld\n", nwans); restore(tmp); nwans = tmp2; return ; } int mid = (le + ri) >> 1, m = 0; for(int i=1;i<=n;i++) { if( qry[i].l > mid || qry[i].r < le ) continue; swap(qry[i], qry[++m]); } solve(le, mid, m); m = 0; for(int i=1;i<=n;i++) { if( qry[i].l > ri || qry[i].r < mid + 1 ) continue; swap(qry[i], qry[++m]); } solve(mid + 1, ri, m); restore(tmp); nwans = tmp2; } int read() { int x = 0; char ch = getchar(); while( ch > '9' || ch < '0' ) ch = getchar(); while( '0' <= ch && ch <= '9' ) x = 10*x + ch - '0', ch = getchar(); return x; } void solve() { init(); for(int i=1;i<=N;i++) a[i] = read(), b[i] = 1; for(int i=1;i<N;i++) { int u = read(), v = read(), w = read(); G1.addedge(u, v, w); } for(int i=1;i<N;i++) { int u = read(), v = read(), w = read(); G2.addedge(u, v, w); } for(int i=1;i<=Q;i++) { int u = read(), w = read(); qry[++tot] = query(b[u], i - 1, u, a[u]); a[u] = w, b[u] = i; } for(int i=1;i<=N;i++) qry[++tot] = query(b[i], Q, i, a[i]); M = N, rebuild(1, 0); divide(1, M, 0); G2.build(); solve(1, Q, tot); } int main() { while( scanf("%d%d", &N, &Q) == 2 ) solve(); }

## @details@ ##

我不知道为什么我常数那么大，没加 O2 就 T，即使加了 O2 时限 15s 跑了 14s 多一点。。。

反正这种题考了几遍就基本成套路了（指边分治）。。。

转载于:https://www.cnblogs.com/Tiw-Air-OAO/p/11333152.html