wordpress 在线点餐,兰州网站优化软件,网站开发框架技术,wordpress支付宝微信支付传送门
题意#xff1a;给一棵带边权的树#xff0c;每个点开始时为白色#xff0c;维护两种操作#xff1a;
1.改变一个点的颜色#xff08;白变黑#xff0c;黑变白#xff09; 2.询问最远的两个白点之间的距离
树分治国集论文
链分治的本质其实就是树链剖分。它们…传送门
题意给一棵带边权的树每个点开始时为白色维护两种操作
1.改变一个点的颜色白变黑黑变白 2.询问最远的两个白点之间的距离
树分治国集论文
链分治的本质其实就是树链剖分。它们的区别是树剖维护路径询问链分治维护全局路径。
动态点分治需要重新建一棵树而链分治分出来的是链本身就可以用数据结构维护。所以链分治本身就可以资瓷修改。
对于每一条链单独用数据结构维护与当前链有交集的路径信息。
对于本题先树链剖分
记Di,Di′D_i,D_i#x27;Di,Di′为节点iii沿虚边往下走到某个白点的最长和次长长度。如果不存在记为−INF-INF−INF
用线段树维护一条链。对于一条链上的一个区间[L,R][L,R][L,R]
记
lmaxmax{dist(L,i)Di}lmaxmax\{dist(L,i)D_i\}lmaxmax{dist(L,i)Di}
rmaxmax{Didist(i,R)}rmaxmax\{D_idist(i,R)\}rmaxmax{Didist(i,R)}
即lmaxlmaxlmax表示LLL沿这条链往下走可以不走在[L,R][L,R][L,R]中的某个点拐出去往下走(可以不走)到某个白点经过的最长长度。注意没有要求起点是白色。rmaxrmaxrmax同理。
再记录ansansans表示有交集的最长长度
然后用类似最大子段和的方式合并。
对于一个线段树节点ppp左右儿子lc,rclc,rclc,rc
lmax[p]max{lmax[lc],dist(L,mid1)lmax[rc]}lmax[p]max\{lmax[lc],dist(L,mid1)lmax[rc]\}lmax[p]max{lmax[lc],dist(L,mid1)lmax[rc]}
rmax[p]max{rmax[lc]dist(mid,R),rmax[rc]}rmax[p]max\{rmax[lc]dist(mid,R),rmax[rc]\}rmax[p]max{rmax[lc]dist(mid,R),rmax[rc]}
ans[p]max{ans[lc],ans[rc],rmax[lc]dist(mid,mid1)lmax[rc]}ans[p]max\{ans[lc],ans[rc],rmax[lc]dist(mid,mid1)lmax[rc]\}ans[p]max{ans[lc],ans[rc],rmax[lc]dist(mid,mid1)lmax[rc]}
边界当LRLRLR,设当前点为iii
若iii是白点
lmaxrmaxmax{Di,0}lmaxrmaxmax\{D_i,0\}lmaxrmaxmax{Di,0}
ansmax{0,Di,DiDi′}ansmax\{0,D_i,D_iD_i#x27;\}ansmax{0,Di,DiDi′}
否则
lmaxrmaxDilmaxrmaxD_ilmaxrmaxDi
ansDiDi′ansD_iD_i#x27;ansDiDi′
最后需要维护Di,Di′D_i,D_i#x27;Di,Di′
当iii是白点,jjj为iii的轻儿子
Dimax{0,w(i,j)lmax[j]}D_imax\{0,w(i,j)lmax[j]\}Dimax{0,w(i,j)lmax[j]}
当iii是黑点
Diw(i,j)lmax[j]D_iw(i,j)lmax[j]Diw(i,j)lmax[j]
然后用个堆之类的瞎维护即可
然而写起来十分精神污染
有一个常用的转换方式 红色边权值为000
这样这棵树变成了二叉树且两两之间的距离不变。也就是说和原来的树是等效的。
有什么用呢
这样一个节点最多有一个重儿子一个轻儿子Di′D_i#x27;Di′永远为−INF-INF−INFDiD_iDi可以直接计算大大降低编程复杂度。当然好不好调是另外一回事
最后答案用multisetmultisetmultiset暴艹即可
复杂度O(nlogn2)O(nlog_n^2)O(nlogn2)
#include iostream
#include cstdio
#include cstring
#include cctype
#include set
#define MAXN 200005
#define INF 0x3f3f3f3f
using namespace std;
inline int read()
{int ans0,f1;char cgetchar();while (c0||c9){if (c-) f-1;cgetchar();}while (c0c9){ansans*10c-0;cgetchar();}return f*ans;
}
inline char gal()
{char cgetchar();while (cA||cZ) cgetchar();return c;
}
int n;
struct edge
{int u,v,w;
}e[MAXN];
int head[MAXN],nxt[MAXN],cnt;
void addnode(int u,int v,int w)
{e[cnt](edge){u,v,w};nxt[cnt]head[u];head[u]cnt;
}
int son[MAXN][2];
int fa[MAXN],dep[MAXN],cost[MAXN],col[MAXN];
void dfs(int u)
{int lasu;for (int ihead[u];i;inxt[i])if (!dep[e[i].v]){fa[fa[e[i].v]n]las;dep[e[i].v]dep[u]1;cost[e[i].v]e[i].w;dfs(son[lasson[las][las!u]n][0]e[i].v);}
}
int siz[MAXN],dis[MAXN],tp[MAXN],bt[MAXN];
int dfn[MAXN],pos[MAXN],tim;
void Dfs(int u)
{if (!u) return;siz[u]1;Dfs(son[u][0]),Dfs(son[u][1]);siz[u]siz[son[u][0]]siz[son[u][1]];if (siz[son[u][0]]siz[son[u][1]]) swap(son[u][0],son[u][1]);
}
multisetint re;
int rt[MAXN],tot;
int ch[MAXN2][2],lmax[MAXN2],rmax[MAXN2],ans[MAXN2];
inline int d(const int x)
{if (!son[x][1]) return col[x]? 0:-INF;if (col[x]) return max(cost[son[x][1]]lmax[rt[son[x][1]]],0);return cost[son[x][1]]lmax[rt[son[x][1]]];
}
#define lc ch[p][0]
#define rc ch[p][1]
inline void update(const int p,const int l,const int r)
{int mid(lr)1;lmax[p]max(lmax[lc],dis[pos[mid1]]-dis[pos[l]]lmax[rc]);rmax[p]max(rmax[lc]dis[pos[r]]-dis[pos[mid]],rmax[rc]);ans[p]max(max(ans[lc],ans[rc]),rmax[lc]cost[pos[mid1]]lmax[rc]);
}
void build(int p,int l,int r)
{ptot;if (lr){if (col[pos[l]]) ans[p]lmax[p]rmax[p]max(0,d(pos[l]));else lmax[p]rmax[p]d(pos[l]),ans[p]-INF;return;}int mid(lr)1;build(lc,l,mid);build(rc,mid1,r);update(p,l,r);
}
void modify(int p,int l,int r,int k)
{if (lr){if (col[pos[l]]) ans[p]lmax[p]rmax[p]max(0,d(pos[l]));else lmax[p]rmax[p]d(pos[l]),ans[p]-INF;return;}int mid(lr)1;if (kmid) modify(lc,l,mid,k);else modify(rc,mid1,r,k);update(p,l,r);
}
void DFS(int u,int t)
{if (!u) return;dis[u]dis[fa[u]]cost[u];bt[tp[u]t]pos[dfn[u]tim]u;DFS(son[u][0],t);DFS(son[u][1],son[u][1]);if (ut) build(rt[u],dfn[u],dfn[bt[u]]),re.insert(ans[rt[u]]);
}
int main()
{freopen(test.in,r,stdin);nread();int cntn;for (int i1;in;i) col[i]1;for (int i1;in;i){int u,v,w;uread(),vread(),wread();addnode(u,v,w),addnode(v,u,w);}dep[1]1;dfs(1);Dfs(1);DFS(1,1);for (int iread();i;--i){if (gal()A) cnt? printf(%d\n,max(0,*re.rbegin())):puts(They have disappeared.);else{int xread();for ((col[x]^1)? cnt:--cnt;x;re.erase(re.find(ans[rt[tp[x]]])),modify(rt[tp[x]],dfn[tp[x]],dfn[bt[tp[x]]],dfn[x]),re.insert(ans[rt[tp[x]]]),xfa[tp[x]]);}}return 0;
}做这种题一定要先理清思路弄懂定义再开始码不要边想边写
