题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=4538
维护一个数据结构支持对于一颗树的操作，需要支持：
1.对于树上的一条路径上的每个点上放一个值。
2.撤销某次操作的路劲放。
3.查询除了经过这个点的路径的最大值。
往一个路径上丢值相当于往不经过条路径的所有点上丢值。
用一个树链剖分即可维护，对于操作区间取反。
直接查询单点最大值即可。
为了维护单点最大值，线段树中的每一个点对应两个堆，用于维护插入誉删除。
防止爆空间，所以标记永久化即可。
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<vector> 5 #include<cstdlib> 6 #include<cmath> 7 #include<cstring> 8 #include<queue> 9 using namespace std; 10 #define maxn 400100 11 #define llg int 12 #define yyj(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout); 13 llg n,m,tail,deep[maxn],top[maxn],size[maxn],son[maxn],dad[maxn],id[maxn],dfsn,T,type; 14 vector<llg>a[maxn]; 15 16 struct node 17 { 18 priority_queue<llg>q1,q2; 19 20 void push1(llg x){ q1.push(x);} 21 void push2(llg x){ q2.push(x);} 22 23 llg top() 24 { 25 llg anss=-1; 26 while (!q2.empty() && (q2.top()==q1.top())) q1.pop(),q2.pop(); 27 if (!q1.empty()) anss=q1.top(); 28 return anss; 29 } 30 }val[maxn*4]; 31 32 struct data 33 { 34 llg l,r; 35 }dl[maxn]; 36 37 struct data_ 38 { 39 llg x,y,z; 40 }ask[maxn]; 41 42 bool cmp(const data&a,const data&b) {return a.l<b.l;} 43 44 void init() 45 { 46 llg x,y; 47 cin>>n>>m; 48 for (llg i=1;i<n;i++) 49 { 50 scanf("%d%d",&x,&y); 51 a[x].push_back(y),a[y].push_back(x); 52 } 53 } 54 55 void dfs_1(llg x,llg fa) 56 { 57 size[x]=1; 58 llg w=a[x].size(),v; 59 for (llg i=0;i<w;i++) 60 { 61 v=a[x][i]; 62 if (v==fa) continue; 63 deep[v]=deep[x]+1; 64 dfs_1(v,x); 65 dad[v]=x; size[x]+=size[v]; 66 if (size[v]>size[son[x]]) son[x]=v; 67 } 68 } 69 70 void dfs_2(llg x,llg fa) 71 { 72 id[x]=++dfsn; 73 if (son[x]) {top[son[x]]=top[x]; dfs_2(son[x],x);} 74 llg w=a[x].size(),v; 75 for (llg i=0;i<w;i++) 76 { 77 v=a[x][i]; 78 if (v==fa || v==son[x]) continue; 79 top[v]=v; dfs_2(v,x); 80 } 81 } 82 83 void add(llg o,llg l,llg r,llg L,llg R,llg V) 84 { 85 if (l>=L && r<=R) 86 { 87 if (T) val[o].push1(V); 88 else val[o].push2(V); 89 return ; 90 } 91 llg lc=o<<1,rc=o<<1|1,mid=(l+r)>>1; 92 if (L<=mid) add(lc,l,mid,L,R,V); 93 if (R>mid) add(rc,mid+1,r,L,R,V); 94 } 95 96 void solve(llg x,llg y,llg V) 97 { 98 llg f1=top[x],f2=top[y]; 99 tail=0; 100 while (f1!=f2) 101 { 102 if (deep[f1]<deep[f2]) swap(x,y),swap(f1,f2); 103 dl[++tail].l=id[f1]; dl[tail].r=id[x]; 104 x=dad[f1]; f1=top[x]; 105 } 106 if (deep[x]<deep[y]) swap(x,y); 107 dl[++tail].l=id[y],dl[tail].r=id[x]; 108 sort(dl+1,dl+tail+1,cmp); 109 llg l=0,r,last=0; 110 for (llg i=1;i<=tail;i++) 111 { 112 l=last+1; r=dl[i].l-1; 113 if (l<=r) add(1,1,n,l,r,V); 114 last=dl[i].r; 115 } 116 l=last+1; r=n; 117 if (l<=r) add(1,1,n,l,r,V); 118 } 119 120 llg maxl_(llg o,llg l,llg r,llg wz) 121 { 122 llg ans=val[o].top(); 123 if (l==r) return ans; 124 llg mid=(l+r)>>1,lc=o<<1,rc=o<<1|1; 125 if (wz<=mid) ans=max(ans,maxl_(lc,l,mid,wz)); 126 if (wz>mid) ans=max(ans,maxl_(rc,mid+1,r,wz)); 127 return ans; 128 } 129 130 int main() 131 { 132 yyj("a"); 133 init(); 134 dfs_1(1,-1); 135 top[1]=1; 136 dfs_2(1,-1); 137 for (llg o=1;o<=m;o++) 138 { 139 scanf("%d",&type); 140 if (type==0) 141 { 142 scanf("%d%d%d",&ask[o].x,&ask[o].y,&ask[o].z); 143 T=1; 144 solve(ask[o].x,ask[o].y,ask[o].z); 145 } 146 if (type==1) 147 { 148 llg x; 149 scanf("%d",&x); 150 T=0; 151 solve(ask[x].x,ask[x].y,ask[x].z); 152 } 153 if (type==2) 154 { 155 llg x; 156 scanf("%d",&x); 157 printf("%d ",maxl_(1,1,n,id[x])); 158 } 159 } 160 return 0; 161 }