调了一天，恶心死我了……作者的题解水的一b……

测试点1～6：

暴力修改查询即可，期望得分30。

测试点7～14：

k=1e5，相当于没有限制，那么对于树上每个点建权值线段树，线段树合并即可。

期望的分40，结合算法1 70分。

#include
#include
#include
#include
#define MAXN 100010
#define LL long long
#define int LL
#define ma(x,y) memset(x,y,sizeof(x))
using namespace std;
struct edge
{
int u,v,nxt;
#define u(x) ed[x].u
#define v(x) ed[x].v
#define n(x) ed[x].nxt
}ed[MAXN*];
int first[MAXN],num_e;
#define f(x) first[x]
int n,m,k[MAXN],Q,tc[MAXN];
struct tree
{
int ls,rs,sum;
#define ls(x) tr[x].ls
#define rs(x) tr[x].rs
#define sum(x) tr[x].sum
}tr[MAXN*];
int cnt,T[MAXN];
int sum[][],fa[MAXN],maxc;
void add(int &x,int l,int r,int L,int R)
{
if(!x)x=++cnt;
if(l==r){sum(x)|=;return;}
int mid=(l+r)>>;
if(L<=mid)add(ls(x),l,mid,L,R); if(R>mid) add(rs(x),mid+,r,L,R);
sum(x)=sum(ls(x))+sum(rs(x));
}
int ask(int x,int l,int r,int L,int R)
{
if(l>=L&&r<=R)return sum(x); int mid=(l+r)>>,ans=;
if(L<=mid)ans+=ask(ls(x),l,mid,L,R); if(R>mid) ans+=ask(rs(x),mid+,r,L,R);
return ans;
}
int merge(int x,int y)
{
if(!x||!y)return x+y;
ls(x)=merge(ls(x),ls(y));
rs(x)=merge(rs(x),rs(y));
if(!ls(x)&&!rs(x))sum(x)=sum(x)|sum(y);
else sum(x)=sum(ls(x))+sum(rs(x));
return x;
}
int ans[MAXN],x[MAXN],c[MAXN];
void dfs(int x,int fa)
{
for(int i=f(x);i;i=n(i))
if(v(i)!=fa)
{
dfs(v(i),x);
ans[v(i)]=ask(T[v(i)],,maxc,,maxc);
T[x]=merge(T[x],T[v(i)]);
}
}
void dfs2(int x,int ff)
{
fa[x]=ff;
for(int i=f(x);i;i=n(i))
if(v(i)!=ff)
dfs2(v(i),x);
}
inline int read();
inline void adde(int u,int v);
signed main()
{
n=read();int tu,tv;
for(int i=;i''){if(a=='-')f=-;a=getchar(); }
while(a>=''&&a<=''){s=s*+a-'';a=getchar();}
return s*f;
}
inline void adde(int u,int v)
{
++num_e;
u(num_e)=u;
v(num_e)=v;
n(num_e)=f(u);
f(u)=num_e;
}

测试点15～20：

最恶心的几个点，用到了树上启发式合并+树链剖分思想。

考虑以时间为线段树下标建立权值线段树，维护这段时间内小球的颜色种类数以及小球总数，用一个桶记录每个颜色出现的最早时间。对于每个节点建立一个vector，将关于这个节点的操作color，time二元组扔到这个节点的vector中。

首先一边dfs求出每个点的重儿子，要用重儿子来保证复杂度，证明见这里。

这里先说一下不保证复杂度但是好理解而且可以救回来的思路：

然后第二遍dfs统计答案：先处理儿子（注意每次要清空桶，但是不要memset），然后将这个节点的所有操作扔到他的重儿子的vector中，互换（相当于将重儿子的操作扔到这个节点），然后枚举儿子，将其他儿子的操作合并，接下来就是统计这个点的答案了：首先确保此时桶是空的，然后枚举这个节点vector中的操作，如果当前小球未出现过直接更新线段树，如果在一个更晚的时间出现则在那个时间种类数减1,这个时间种类数+1。最后个数加1.然后说一下线段树的查询操作，和主席树的思想类似（直接上代码）：

int ask(int x,int l,int r,int num)
{
if(num<=)return ; if(l==r)return sum(x); int ans=,mid=(l+r)>>;
if(num(ls(x))<=num)
{
ans+=sum(ls(x));
ans+=ask(rs(x),mid+,r,num-num(ls(x)));
return ans;
}
else return ask(ls(x),l,mid,num);
}

#include
#include
#include
#include
#include
#define MAXN 100010
#define LL long long
#define MP(a,b) make_pair(a,b)
#define ma(x) memest(x,0,sizeof(x))
using namespace std;
struct edge
{
int u,v,nxt;
#define u(x) ed[x].u
#define v(x) ed[x].v
#define n(x) ed[x].nxt
}ed[MAXN*];
int first[MAXN],num_e;
#define f(x) first[x]
int n,m,k[MAXN],Q,tc[MAXN];
vector >cz[MAXN];
struct tree
{
int ls,rs,sum,num;
#define ls(x) tr[x].ls
#define rs(x) tr[x].rs
#define sum(x) tr[x].sum
#define num(x) tr[x].num
}tr[MAXN*];
int cnt,T[MAXN],maxc;
int ans[MAXN],x[MAXN],c[MAXN];
int t[MAXN];
int son[MAXN],size[MAXN];
void add(int &x,int l,int r,int t,int tx,int y)
{
if(!x)x=++cnt;
if(l==r){sum(x)+=tx;num(x)+=y;return;}
int mid=(l+r)>>;
if(t<=mid)add(ls(x),l,mid,t,tx,y); else add(rs(x),mid+,r,t,tx,y); sum(x)=sum(ls(x))+sum(rs(x)); num(x)=num(ls(x))+num(rs(x)); } int ask(int x,int l,int r,int num) { if(num<=)return ; if(l==r)return sum(x); int ans=,mid=(l+r)>>;
if(num(ls(x))<=num) { ans+=sum(ls(x)); ans+=ask(rs(x),mid+,r,num-num(ls(x))); return ans; } else return ask(ls(x),l,mid,num); } void merge(int x,int y) { for(int i=;it2)
{
add(T[x],,m,t[t1],-,);
add(T[x],,m,t2,,);
t[t1]=t2;
}
add(T[x],,m,t2,,);
}
ans[x]=ask(T[x],,m,k[x]);
}
inline int read();
void dfs(int x,int fa);
inline void adde(int u,int v);
signed main()
{
// freopen("in.txt","r",stdin);

 n=read();int tu,tv;  
 for(int i=;i<n;i++)  
 {  
     tu=read(),tv=read();  
     adde(tu,tv),adde(tv,tu);  
 }  
 for(int i=;i<=n;i++)k\[i\]=read();  
 m=read();  
 for(int i=;i<=m;i++)  
 {  
     x\[i\]=read(),c\[i\]=read(),tc\[i\]=c\[i\];  
     maxc=max(maxc,c\[i\]);  
 }  
 sort(tc+,tc++m);maxc=m;  
 int ooo=unique(tc+,tc++m)-tc-;  
 for(int i=;i<=m;i++)  
     c\[i\]=lower\_bound(tc+,tc+ooo+,c\[i\])-tc;  
 for(int i=;i<=m;i++)  
     cz\[x\[i\]\].push\_back(MP(c\[i\],i));  
 dfs(,);  
 dfs2(,);  
 Q=read();  
 for(int i=;i<=Q;i++)  
     x\[i\]=read(),printf("%d\\n",ans\[x\[i\]\]);  

}
inline int read()
{
int s=,f=;char a=getchar();
while(a<''||a>''){if(a=='-')f=-;a=getchar(); }
while(a>=''&&a<=''){s=s*+a-'';a=getchar();} return s*f; } inline void adde(int u,int v) { ++num_e; u(num_e)=u; v(num_e)=v; n(num_e)=f(u); f(u)=num_e; } void dfs(int x,int fa) { size[x]=; for(int i=f(x);i;i=n(i)) if(v(i)!=fa) { dfs(v(i),x); size[x]+=size[v(i)]; if(size[v(i)]>size[son[x]])son[x]=v(i);
}
}

接近正解的T30代码

到这里就结束了，然后你应该就会发现你T30了，因为以上算法是不保证时间复杂度的，原因在于处理重儿子后清空桶花费了过长时间。但是如果不清空桶下面的答案查询就会出错，那怎么办呢？

其实可以在处理完所有轻儿子后在处理重儿子，此后不清空桶，而是直接T[x]=T[son[x]](根节点)，直接从重儿子的线段树上开始修改，这样时间复杂度就有保证了。还有一点是这样要在最后才把重儿子的操作合并。

#include
#include
#include
#include
#include
#define MAXN 100010
#define LL long long
#define int LL
#define MP(a,b) make_pair(a,b)
#define ma(x) memest(x,0,sizeof(x))
using namespace std;
struct edge
{
int u,v,nxt;
#define u(x) ed[x].u
#define v(x) ed[x].v
#define n(x) ed[x].nxt
}ed[MAXN*];
int first[MAXN],num_e;
#define f(x) first[x]
int n,m,k[MAXN],Q,tc[MAXN];
vector >cz[MAXN];
struct tree
{
int ls,rs,sum,num;
#define ls(x) tr[x].ls
#define rs(x) tr[x].rs
#define sum(x) tr[x].sum
#define num(x) tr[x].num
}tr[MAXN*];
int cnt,T[MAXN],maxc;
int ans[MAXN],x[MAXN],c[MAXN];
int t[MAXN];
int son[MAXN],size[MAXN];
void add(int &x,int l,int r,int t,int tx,int y)
{
if(!x)x=++cnt;
if(l==r){sum(x)+=tx;num(x)+=y;return;}
int mid=(l+r)>>;
if(t<=mid)add(ls(x),l,mid,t,tx,y); else add(rs(x),mid+,r,t,tx,y); sum(x)=sum(ls(x))+sum(rs(x)); num(x)=num(ls(x))+num(rs(x)); } int ask(int x,int l,int r,int num) { if(num<=)return ; if(l==r)return sum(x); int ans=,mid=(l+r)>>;
if(num(ls(x))<=num) { ans+=sum(ls(x)); ans+=ask(rs(x),mid+,r,num-num(ls(x))); return ans; } else return ask(ls(x),l,mid,num); } void merge(int x,int y) { for(int i=;it2)
{
add(T[x],,m,t[t1],-,);
add(T[x],,m,t2,,);
t[t1]=t2;
}
add(T[x],,m,t2,,);
}
ans[x]=ask(T[x],,m,k[x]);
if(son[x])
{
merge(son[x],x);
swap(cz[son[x]],cz[x]);
}
}
inline int read();
void dfs(int x,int fa);
inline void adde(int u,int v);
signed main()
{
// freopen("in.txt","r",stdin);

 n=read();int tu,tv;  
 for(int i=;i<n;i++)  
 {  
     tu=read(),tv=read();  
     adde(tu,tv),adde(tv,tu);  
 }  
 for(int i=;i<=n;i++)k\[i\]=read();  
 m=read();  
 for(int i=;i<=m;i++)  
 {  
     x\[i\]=read(),c\[i\]=read(),tc\[i\]=c\[i\];  
     maxc=max(maxc,c\[i\]);  
 }  
 sort(tc+,tc++m);maxc=m;  
 int ooo=unique(tc+,tc++m)-tc-;  
 for(int i=;i<=m;i++)  
     c\[i\]=lower\_bound(tc+,tc+ooo+,c\[i\])-tc;  
 for(int i=;i<=m;i++)  
     cz\[x\[i\]\].push\_back(MP(c\[i\],i));  
 dfs(,);dfs2(,);  
 Q=read();  
 for(int i=;i<=Q;i++)  
     x\[i\]=read(),printf("%lld\\n",ans\[x\[i\]\]);  

}
inline int read()
{
int s=,f=;char a=getchar();
while(a<''||a>''){if(a=='-')f=-;a=getchar(); }
while(a>=''&&a<=''){s=s*+a-'';a=getchar();} return s*f; } inline void adde(int u,int v) { ++num_e; u(num_e)=u; v(num_e)=v; n(num_e)=f(u); f(u)=num_e; } void dfs(int x,int fa) { size[x]=cz[x].size(); for(int i=f(x);i;i=n(i)) if(v(i)!=fa) { dfs(v(i),x); size[x]+=size[v(i)]; if(size[v(i)]>size[son[x]])son[x]=v(i);
}
}

完整代码