关键词：
我居然忘写题解啦！(记忆废)
总的来说这题就是道大数据结构……看我代码长度就知道了，真的是长得要死……
……
这题的操作都是路径修改单点查询，因此可以树上差分，问题就变成了维护子树中的所有标记。
注意到题目要求按照出现次数排序，可以想到用以出现次数为关键字的平衡树维护。虽然这个东西没法快速合并，但它是资瓷启发式合并的，那么我们对每个点再开一个map记录每种礼物的出现次数就好了，合并的时候同时维护平衡树和map。
合并操作只会进行$n-1$次(废话)，因此复杂度为$O(n\log^2 n)$。但是这个做法常数比较大，卡常卡到死才过的……(看上去大多数人都写的平衡树启发式合并，然后这题就变成了卡常大赛……)
这份代码是卡过常的，所以比较丑，不愿看就不要勉强了……
1 #include<stdio.h> 2 #include<algorithm> 3 #include<vector> 4 #include<queue> 5 #include<map> 6 #define int unsigned 7 #define Anti __attribute__((optimize("-Os"))) 8 #define Leaf __inline__ __attribute__((always_inline)) 9 #define dir(x) ((x)==(x)->p->ch[1]) 10 namespace mine{ 11 #define siz (1<<19) 12 #define frd fread(hd=buf,1,siz,stdin) 13 #define getchar() (hd==tl?(frd,*hd++):*hd++) 14 char buf[siz],*hd=buf+siz,*tl=buf+siz; 15 template<class T>Anti Leaf void readint(register T &__x){ 16 register int __c; 17 __x=0; 18 do __c=getchar();while(__c<48); 19 for(;__c>47;__c=getchar())__x=(__x<<1)+(__x<<3)+(__c^48); 20 } 21 template<class T>Anti Leaf void writeint(T __x){ 22 static int __a[25]; 23 register int __i,__j; 24 __i=0; 25 do{ 26 __a[__i++]=__x%10^48; 27 __x/=10; 28 }while(__x); 29 for(__j=__i-1;~__j;__j--)putchar(__a[__j]); 30 } 31 } 32 using namespace mine; 33 using namespace std; 34 const int maxn=100005; 35 struct node{ 36 int key,id,size,sum; 37 node *ch[2],*p; 38 Anti Leaf node(register int id=0,register int key=0):key(key),id(id),size(1),sum(id){} 39 Anti Leaf int cmp(register int i,register int k){ 40 if(k!=key)return k>key; 41 return i>id; 42 } 43 Anti Leaf void refresh(){ 44 size=ch[0]->size+ch[1]->size+1; 45 sum=ch[0]->sum^ch[1]->sum^id; 46 } 47 }*null=new node(),*root[maxn]; 48 struct Q{ 49 int k,id; 50 Q(register int k,register int id):k(k),id(id){} 51 }; 52 queue<node*>freenodes; 53 void dfs1(int); 54 void dfs2(int); 55 int LCA(int,int); 56 node *newnode(int,int); 57 void delnode(node*); 58 void merge(int,int); 59 void insert(int,int); 60 void erase(node*); 61 node *kth(int,node*); 62 void splay(node*,node* =null); 63 void rot(node*,int); 64 node *findmax(node*); 65 vector<int>G[maxn]; 66 map<int,node*>mp[maxn]; 67 map<int,int>tmp[maxn]; 68 vector<Q>que[maxn]; 69 int T; 70 int f[maxn][18],d[maxn]; 71 int n,m,lgn=0,ans[maxn]; 72 //#include<ctime> 73 signed main(){ 74 null->size=0; 75 null->ch[0]=null->ch[1]=null->p=null; 76 fill(root,root+maxn,null); 77 readint(n); 78 for(int i=1,x,y;i<n;i++){ 79 readint(x); 80 readint(y); 81 G[x].push_back(y); 82 G[y].push_back(x); 83 } 84 dfs1(1); 85 for(register int j=1;j<=lgn;j++)for(register int i=1;i<=n;i++)f[i][j]=f[f[i][j-1]][j-1]; 86 readint(m); 87 while(m--){ 88 int x,y,u,v; 89 readint(x); 90 readint(y); 91 readint(v); 92 readint(u); 93 register int z=LCA(x,y); 94 tmp[x][u]+=v; 95 tmp[y][u]+=v; 96 tmp[z][u]-=v; 97 if(f[z][0])tmp[f[z][0]][u]-=v; 98 } 99 for(register int x=1;x<=n;x++){ 100 T=x; 101 for(map<int,int>::iterator it=tmp[x].begin();it!=tmp[x].end();it++)if(it->second){ 102 insert(it->first,it->second); 103 mp[x][it->first]=root[x]; 104 } 105 tmp[x].clear(); 106 } 107 readint(m); 108 for(register int i=1;i<=m;i++){ 109 int x,k; 110 readint(x); 111 readint(k); 112 que[x].push_back(Q(k,i)); 113 } 114 dfs2(1); 115 for(register int i=1;i<=m;i++){ 116 writeint(ans[i]); 117 putchar('\n'); 118 } 119 //fprintf(fopen("con","w"),"%lf",(double)clock()/CLOCKS_PER_SEC); 120 return 0; 121 } 122 Anti void dfs1(int x){ 123 d[x]=d[f[x][0]]+1; 124 while((1<<lgn)<d[x])lgn++; 125 for(int i=0;i<(int)G[x].size();i++)if(G[x][i]!=f[x][0]){ 126 f[G[x][i]][0]=x; 127 dfs1(G[x][i]); 128 } 129 } 130 Anti void dfs2(int x){ 131 for(int i=0;i<(int)G[x].size();i++)if(G[x][i]!=f[x][0]){ 132 dfs2(G[x][i]); 133 merge(x,G[x][i]); 134 } 135 T=x; 136 for(int i=0;i<(int)que[x].size();i++){ 137 if(que[x][i].k>=root[x]->size)ans[que[x][i].id]=root[x]->sum; 138 else{ 139 splay(kth(que[x][i].k+1,root[x])); 140 ans[que[x][i].id]=root[x]->ch[0]->sum; 141 } 142 } 143 } 144 Anti Leaf int LCA(register int x,register int y){ 145 if(d[x]!=d[y]){ 146 if(d[x]<d[y]){x^=y;y^=x;x^=y;} 147 for(int i=lgn;~i;i--)if(d[f[x][i]]>=d[y])x=f[x][i]; 148 } 149 if(x==y)return x; 150 for(register int i=lgn;~i;i--)if(f[x][i]!=f[y][i]){ 151 x=f[x][i]; 152 y=f[y][i]; 153 } 154 return f[x][0]; 155 } 156 Anti Leaf node *newnode(register int id,register int key){ 157 register node *x; 158 if(freenodes.empty())x=new node(id,key); 159 else{ 160 x=freenodes.front(); 161 freenodes.pop(); 162 *x=node(id,key); 163 } 164 x->ch[0]=x->ch[1]=x->p=null; 165 return x; 166 } 167 Anti Leaf void delnode(register node *x){ 168 if(freenodes.size()<maxn<<2)freenodes.push(x); 169 else delete x; 170 } 171 Anti Leaf void merge(register int x,register int y){ 172 if(root[x]==null){ 173 root[x]=root[y]; 174 swap(mp[x],mp[y]); 175 return; 176 } 177 else if(root[y]==null)return; 178 if(root[x]->size>root[y]->size){ 179 register node *u=findmax(root[y]); 180 T=y;splay(u); 181 while(u!=null){ 182 if(mp[x].count(u->id)){ 183 register node v=*mp[x][u->id]; 184 T=x;erase(mp[x][u->id]); 185 if(u->key+v.key){ 186 insert(v.id,u->key+v.key); 187 mp[x][u->id]=root[x]; 188 } 189 else mp[x].erase(u->id); 190 } 191 else{ 192 T=x;insert(u->id,u->key); 193 mp[x][u->id]=root[x]; 194 } 195 if(u->ch[0]==null)break; 196 T=y; 197 splay(findmax(u->ch[0])); 198 root[y]->ch[1]=null; 199 delnode(u); 200 u=root[y]; 201 } 202 mp[y].clear(); 203 root[y]=null; 204 } 205 else{ 206 register node *u=findmax(root[x]); 207 T=x;splay(u); 208 while(u!=null){ 209 if(mp[y].count(u->id)){ 210 register node v=*mp[y][u->id]; 211 T=y;erase(mp[y][u->id]); 212 if(u->key+v.key){ 213 insert(v.id,u->key+v.key); 214 mp[y][u->id]=root[y]; 215 } 216 else mp[y].erase(u->id); 217 } 218 else{ 219 T=y;insert(u->id,u->key); 220 mp[y][u->id]=root[y]; 221 } 222 if(u->ch[0]==null)break; 223 T=x; 224 splay(findmax(u->ch[0])); 225 root[x]->ch[1]=null; 226 delnode(u); 227 u=root[x]; 228 } 229 mp[x].clear(); 230 root[x]=null; 231 swap(root[x],root[y]); 232 swap(mp[x],mp[y]); 233 } 234 } 235 Anti Leaf void insert(register int id,register int key){ 236 if(root[T]==null){ 237 root[T]=newnode(id,key); 238 return; 239 } 240 node *rt=root[T]; 241 register int d=0; 242 while(rt!=null){ 243 d=rt->cmp(id,key); 244 if(rt->ch[d]!=null)rt=rt->ch[d]; 245 else{ 246 rt->ch[d]=newnode(id,key); 247 rt->ch[d]->p=rt; 248 break; 249 } 250 } 251 for(node *y=rt;y!=null;y=y->p)y->refresh(); 252 splay(rt->ch[d]); 253 } 254 Anti Leaf void erase(register node *x){ 255 splay(x); 256 if(x->ch[0]!=null){ 257 splay(findmax(x->ch[0]),x); 258 x->ch[0]->ch[1]=x->ch[1]; 259 if(x->ch[1]!=null)x->ch[1]->p=x->ch[0]; 260 x->ch[0]->p=null; 261 root[T]=x->ch[0]; 262 } 263 else if((root[T]=x->ch[1])!=null)x->ch[1]->p=null; 264 delnode(x); 265 if(root[T]!=null)root[T]->refresh(); 266 } 267 Anti Leaf node *kth(register int k,register node *rt){ 268 register int d; 269 while(rt!=null){ 270 if(k==rt->ch[0]->size+1){ 271 splay(rt); 272 return rt; 273 } 274 if((d=k>rt->ch[0]->size))k-=rt->ch[0]->size+1; 275 rt=rt->ch[d]; 276 } 277 return null; 278 } 279 Anti Leaf node *findmax(register node *x){ 280 while(x->ch[1]!=null)x=x->ch[1]; 281 return x; 282 } 283 Anti Leaf void splay(register node *x,register node *t){ 284 while(x->p!=t){ 285 if(x->p->p==t){ 286 rot(x->p,dir(x)^1); 287 break; 288 } 289 if(dir(x)==dir(x->p))rot(x->p->p,dir(x->p)^1); 290 else rot(x->p,dir(x)^1); 291 rot(x->p,dir(x)^1); 292 } 293 } 294 Anti Leaf void rot(register node *x,register int d){ 295 register node *y=x->ch[d^1]; 296 if((x->ch[d^1]=y->ch[d])!=null)y->ch[d]->p=x; 297 if((y->p=x->p)!=null)x->p->ch[dir(x)]=y; 298 else root[T]=y; 299 (y->ch[d]=x)->p=y; 300 x->refresh(); 301 y->refresh(); 302 }
顺便说一下，用平衡树维护出现次数的想法是从我的一道原创题来的：给定一个序列，每次询问区间中出现次数第k多的数。
特此声明，版权所有……
51nod1185||51nod1072威佐夫博弈
贴个模板：平常的跟高精度java的；int：#pragmacomment(linker,"/STACK:1024000000,1024000000")#include<iostream>#include<cstdio>#include<cmath>#include<string>#include<queue>#include<alg 查看详情
51nod1631小鲨鱼在51nod小学
...题鲨鱼巨巨2.0（以下简称小鲨鱼）以优异的成绩考入了51nod小学。并依靠算法方面的特长，在班里担任了许多职务。 每一个职务都有一个起始时间A和结束时间B，意为小鲨鱼在[A,B]时间内，担任了某职务(inclusively)。 现在... 查看详情
51nod1354：选数字
51nod1354：选数字题目链接：http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1354题目大意：有$T(Tleqslant20)$组数据，每组给出$n(nleqslant1000)$个数和$K(Kleqslant100,000,000)$，问在这$n$个数中选取若干个，积为$K$的方案数有多少.DP+离散化与... 查看详情
51nod1310：chandrimaandxor
51nod1310：ChandrimaandXOR题目链接：http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1310题目大意：序列$S={1,2,4,5,...}$，其中任何一个数转为二进制不包括两个连续的$1$。给出一个长度为$N$的正整数数组$A$，$A_1,A_2,...,A_n$记录的是下标... 查看详情
[51nod]配对
https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1737求出树的重心，跑spfa#include<iostream>#include<cstdio>#include<cmath>#include<cstring>#include<string>usingname 查看详情
51nod1232：完美数
51nod1232：完美数题目链接：http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1232题目大意：如果一个数能够被组成它的各个非$0$数字整除，则称它是完美数。例如：$10$,$11$,$12$,$101$都是完美数，但是$13$就不是完美数（因为$13$不能... 查看详情
51nod2576
题意51nod做法令(f_n,d)为(d)层，目前维宽度为(n)(f_n,d=sumlimits_i=1^nf_i,d-1(n?i+1)^k)构造矩阵转移，上三角对角线相等矩阵，快速算就完了题外话一遍过qwq 查看详情
51nod1728
题意51nod做法要是想不到树就删号重练吧令(F_k)为深度不超过(k)的森林个数的EGF不超过(k)的森林，就是若干棵不超过(k)的树，取掉树的根，就是不超过(k-1)的森林就有(F_k=e^xF_k-1) 查看详情
51nod1773a国的贸易
51nod1773http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1773 #include<cstdio>#include<map>#definegcgetchar()constintmod=1e9+7,inv2=(mod+1)>>1;inta[1<<21],b[ 查看详情
51nod1241：特殊的排序
51nod1241：特殊的排序题目链接：http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1241题目大意：给出$n$个数（$1leqslanta_ileqslantn$），现在要对这个数组进行排序，在排序时只能将元素放在数组的头部或尾部，问至少需要移动多少个... 查看详情
51nod1537分解
题目传送门：https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1537神犇题解传送门：http://blog.csdn.net/qingshui23/article/details/52350523证明好巧妙，给跪OTZ题目的式子：${left({1{ m{+}}sqrt2} ight)^{ m{n}}}$，设其 查看详情
51nod1406：与查询
51nod1406：与查询题目链接：http://www.51nod.com/onlineJudge/submitDetail.html#!judgeId=222358题目大意：给出$n$个数，问这$n$个数与$x$做位与（$&$）后值为$x$的有多少个.DP显然暴力是不行的.由题目可得，若$a&x=x$，则$x$的二进制表示中为$1... 查看详情
51nod1227平均最小公倍数
传送门 查看详情
51nod1294：修改数组
51nod1294：修改数组题目链接：http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1294题目大意：将一个序列修改成严格递增序列，最少需要替换几个数.dp这道题相当巧妙.最小的满足条件的序列为${1,2,3,...,n}$，若$a_i<i$那么该数必须... 查看详情
莫比乌斯函数之和51nod-1244（杜教筛）
莫比乌斯函数之和 51Nod-1244 题意： 查看详情
51nod1428活动安排问题
51Nod 1428 活动安排问题Link： http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1428 1428 活动安排问题基准时间限制：1 秒空间限制：131072 KB分值: 10 难度：2级算法题有若干个活动，第i 查看详情
51nod1616最小集合
51nod1616最小集合题目链接：http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1616题目大意：若$a$和$b$均在集合$S$中，则$gcd(a,b)$也在$S$中。现给出$S$中$n$个元素，问$|S|$的最小值.数论定义$f(k)$为这$n$个数中能被$k$整除的数的个数.对... 查看详情
51nod1640mst+二分
http://www.51nod.com/onlineJudge/questionCode.html#!problemId=16401640天气晴朗的魔法题目来源：原创基准时间限制：1秒空间限制：131072KB分值:20难度：3级算法题收藏关注这样阴沉的天气持续下去，我们不免担心起他的健康。 51nod魔法学校... 查看详情