又是一道樹剖題。。。 對每個點建一個優先隊列。 對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; }新聞熱點
疑難解答
