原来一直以为是个dp。

蜜汁尴尬，内存开炸= =倍增压tarijin2333

身败名裂……

1.不足五个的UTF-滑 值为0
2.long long ,double都会炸,要用long double
3.记录子树边界参数[min, max]的方法会T

回复 @FAQ :
cnm

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <queue>
#define inf (1<<30)
#define il inline
#define RG register
#define LL long long
#define lowbit(o) o & (-o)
#define N 40001
using namespace std;
struct ed{int nxt,to;}e[N*2];int head[N],tot;
int id[N],top[N],BL[N],sz[N],fa[N],deep[N],hson[N],w[N];
int n,P,Q,idn;
inline int read() {
int x=0;
char ch=getchar();
while(ch<'0'||ch>'9') ch=getchar();
while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
return x;
}
il void add(RG int u,RG int v){e[tot].nxt=head[u];e[tot].to=v;head[u]=tot++;}
il void ADD(RG int u,RG int v){add(u,v),add(v,u);}
il void dfs1(RG int u,RG int faa){
deep[u]=deep[faa]+1,sz[u]=1;fa[u]=faa;
for(RG int i=head[u];i!=-1;i=e[i].nxt)if(e[i].to!=faa){
RG int v=e[i].to;dfs1(v,u);
sz[u]+=sz[v];if(sz[hson[u]]<sz[v])hson[u]=v;
}
}
il void dfs2(RG int u,RG int toop){top[u]=toop;
id[u]=++idn;BL[idn]=u;if(hson[u])dfs2(hson[u],toop);
for(RG int i=head[u];i!=-1;i=e[i].nxt)
if(e[i].to!=fa[u]&&e[i].to!=hson[u])
dfs2(e[i].to,e[i].to);w[u]=idn;
}
il int LCA(RG int x,RG int y){
while(top[x]!=top[y]){
if(deep[top[x]]<deep[top[y]])swap(x,y);
x=fa[top[x]];
}if(deep[x]>deep[y])swap(x,y);
return x;
}
il int gogogo(int x,int y){RG int ll=0;
while(top[x]!=top[y]){
if(deep[top[x]]<deep[top[y]])swap(x,y);
ll=top[x],x=fa[top[x]];
}if(deep[x]>deep[y])swap(x,y);
return x==y?ll:BL[id[x]+1];
}
struct matrix{
int x,xx,y,yy,k;
matrix() {}
matrix(int X,int XX,int Y,int YY,int K):x(X),xx(XX),y(Y),yy(YY),k(K) {}
}p[N*2];int cnt;
struct node{
int x,y,k,id;
node() {}
node(int _x,int _y,int _k,int i):x(_x),y(_y),k(_k),id(i) {}
}ff[N],quer[N],quel[N];
int tree[N],ans[N];
il void Add(int x,int y){for(RG int i=x;i<=n;i+=lowbit(i))tree[i]+=y;}
int Query(int x){int s=0;for(RG int i=x;i;i-=lowbit(i))s+=tree[i];return s;}
il bool comp(const matrix & a,const matrix & b){return a.k<b.k;}
struct ha{
int x,y,yy,v,kind;
ha() {}
ha(int a,int b,int c,int d,int e):x(a),y(b),yy(c),v(d),kind(e) {}
}que[N*3];int sum[N];
il bool Comp(const ha & a,const ha & b){return a.x==b.x?a.kind<b.kind:a.x<b.x;}
il void solve(RG int h,RG int t,RG int l,RG int r){
if(t<h)return;
if(l==r){
for(int i=h;i<=t;++i)ans[ff[i].id]=p[l].k;
return;
}RG int mid=(l+r)>>1;int ss=0;
for(RG int i=l;i<=mid;++i){
que[++ss]=ha(p[i].x,p[i].y,p[i].yy,1,0);
que[++ss]=ha(p[i].xx,p[i].y,p[i].yy,-1,n+1);
}for(RG int i=h;i<=t;++i)
que[++ss]=ha(ff[i].x,ff[i].y,0,0,i);
sort(que+1,que+ss+1,Comp);memset(tree,0,sizeof(tree));
for(RG int i=1;i<=ss;++i)
if(que[i].kind>=h&&que[i].kind<=t)
sum[que[i].kind]=Query(que[i].y);
else Add(que[i].y,que[i].v),Add(que[i].yy+1,-que[i].v);
RG int L=0,R=0;
for(RG int i=h;i<=t;++i){
if(sum[i]>=ff[i].k)quel[++L]=ff[i];
else quer[++R]=ff[i],quer[R].k-=sum[i];
}for(RG int i=1;i<=L;++i)ff[i+h-1]=quel[i];
for(RG int i=1;i<=R;++i)ff[L+h+i-1]=quer[i];
solve(h,h+L-1,l,mid);solve(h+L,t,mid+1,r);
}
int main(){
freopen("fruit_hnoi2015.in","r",stdin);
freopen("fruit_hnoi2015.out","w",stdout);
memset(head,-1,sizeof(head));
n=read(),P=read(),Q=read();int u,v;
for(RG int i=1;i<n;++i)u=read(),v=read(),ADD(u,v);
dfs1(1,1),dfs2(1,1);
for(RG int i=1;i<=P;++i){
RG int a,b,c;a=read(),b=read(),c=read();
RG int lca=LCA(a,b);if(id[a]>id[b])swap(a,b);
if(lca==a){RG int mm=gogogo(a,b);
if(id[mm]>1)p[++cnt]=matrix(1,id[mm]-1,id[b],w[b],c);
if(w[mm]+1<=n)p[++cnt]=matrix(id[b],w[b],w[mm]+1,n,c);
}
else p[++cnt]=matrix(id[a],w[a],id[b],w[b],c);
}
for(RG int i=1;i<=Q;++i){
RG int u,v,k;u=read(),v=read(),k=read();
if(id[u]>id[v])swap(u,v);
ff[i]=node(id[u],id[v],k,i);
}sort(p+1,p+cnt+1,comp);solve(1,Q,1,cnt);
for(RG int i=1;i<=Q;++i)cout<<ans[i]<<"\n";
return 0;
}

回复 @HZOI_蒟蒻一只 :
旁友，你的叹号太多了

强行写一发FFT……

垃圾Mike忘了输出取模……
强行写个Treap练手……

矩阵快速幂水过

巧妙的方法

WC讲课原题

所以说为什么直接用int不行。。
难不成是爆掉了。。

直接暴力输出竟有60分

啊啊啊啊爽....................
数组版splay，自以为打的很美

要想清楚开闭区间哦

随手开了2e6的数组以为够用了
然而还是爆了……
所以还是要好好算……

没有注意到坐标可能为负

吓傻了