又是一道树剖题。。。 对每个点建一个优先队列。 对1号操作取反，比如a到b之间加入重要度为v的话，就往不是a到b路径的节点加入v；2号操作是1号操作的逆运算，对某个时间打上标记即可；对于3号操作询问，只要找一下当前节点对应的优先队列中权值最大且对应的时间没有被打上标记的就是答案。
#include<cmath>#include<cstdio>#include<vector>#include <queue>#include<cstring>#include<iomanip>#include<stdlib.h>#include<iostream>#include<algorithm>#define ll long long#define inf 1000000000#define mod 1000000007#define N 100005#define fo(i,a,b) for(i=a;i<=b;i++)#define fd(i,a,b) for(i=a;i>=b;i--)using namespace std;struct qry{int x,y;} a[105];bool Operator <(qry u,qry v) {return u.x < v.x;}PRiority_queue<qry> q[300005];int tar[N<<1],nxt[N<<1],head[N],size[N],fa[N],dep[N],son[N],top[N],id[N],hack[N<<1];int tot,num,cnt,t,res,n,m,i,x,y,opt,aa,bb,rk;void add_edge(int x,int y){tar[++tot] = y; nxt[tot] = head[x]; head[x] = tot;}void dfs1(int nw){ size[nw] = 1; int p; for (p = head[nw];p; p = nxt[p]) { int nt = tar[p]; if (nt == fa[nw]) continue; fa[nt] = nw; dep[nt] = dep[nw] + 1; dfs1(nt); size[nw] += size[nt]; if (size[nt] >= size[son[nw]]) son[nw] = nt; }}void dfs2(int nw,int tp){ int p; top[nw] = tp; id[nw] = ++num; if (son[nw]) dfs2(son[nw],tp); for (p = head[nw];p; p = nxt[p]) { int nt = tar[p]; if (nt != fa[nw] && nt != son[nw]) dfs2(nt,nt); }}void link(int u,int v){ cnt = 0; while (top[u] != top[v]) { if (dep[top[u]] < dep[top[v]]) swap(u,v); a[++cnt].x = id[top[u]]; a[cnt].y = id[u]; u = fa[top[u]]; } if (dep[u] > dep[v]) swap(u,v); a[++cnt].x = id[u]; a[cnt].y = id[v];}void update(int rt,int l,int r,int L,int R){ if (L <= l && r <= R) {q[rt].push((qry){rk,t}); return;} int mid = (l + r) >> 1; if (L <= mid) update(rt<<1,l,mid,L,R); if (mid < R) update(rt<<1|1,mid+1,r,L,R); }void query(int rt,int l,int r,int target){ while (!q[rt].empty() && hack[q[rt].top().y]) q[rt].pop(); //弹出栈顶已被结束的请求 if (!q[rt].empty()) res = max(res,q[rt].top().x); if (l == r) return; int mid = (l + r) >> 1; if (target <= mid) query(rt<<1,l,mid,target); else query(rt<<1|1,mid+1,r,target);}int main(){ scanf("%d%d",&n,&m); fo(i,1,n-1) {scanf("%d%d",&x,&y); add_edge(x,y); add_edge(y,x);} dfs1(1); dfs2(1,1); fo(t,1,m) { scanf("%d",&opt); if (opt == 0) { scanf("%d%d%d",&aa,&bb,&rk); link(aa,bb); sort(a+1,a+cnt+1); fo(i,1,cnt) if (a[i-1].y+1 <= a[i].x-1) update(1,1,n,a[i-1].y+1,a[i].x-1); if (a[cnt].y+1 <= n) update(1,1,n,a[cnt].y+1,n); //对操作区间取反 } if (opt == 1) {scanf("%d",&aa); hack[aa] = 1;} //结束某个请求 if (opt == 2) { scanf("%d",&aa); res = -1; query(1,1,n,id[aa]); printf("%d/n",res); } } return 0; }新闻热点
疑难解答
