bzoj1759: Let there be rainbows!

传送门
我 * 你 * 的辣鸡卡时限出题人
其实题目就是一个裸的树剖。
我不会告诉你我线段树写炸了3回
TLE代码：

#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define N 200005
using namespace std;
struct edge{int to,next;}e[N*2];
int head[N],sz[N],fa[N][20],dep[N],pos[N],top[N];
int tot,cnt,n,m,x,y,z,bin[25],ans[8];
struct node{int tag,s[8];}t[N*4];
void add(int x,int y){
    e[++tot]=(edge){y,head[x]};
    head[x]=tot;
}
void dfs1(int x){
    sz[x]=1;
    for (int i=1;i<=19;i++)
        fa[x][i]=fa[fa[x][i-1]][i-1];
    for (int i=head[x];i;i=e[i].next)
        if (e[i].to!=fa[x][0]){
            dep[e[i].to]=dep[x]+1;
            fa[e[i].to][0]=x;
            dfs1(e[i].to);
            sz[x]+=sz[e[i].to];
        }
}
void dfs2(int x,int tp){
    pos[x]=++cnt; top[x]=tp;
    int k=0;
    for (int i=head[x];i;i=e[i].next)
        if (e[i].to!=fa[x][0]&&sz[e[i].to]>sz[k])
            k=e[i].to;
    if (k) dfs2(k,tp);
    for (int i=head[x];i;i=e[i].next)
        if (e[i].to!=fa[x][0]&&e[i].to!=k)
            dfs2(e[i].to,e[i].to);
}
int lca(int x,int y){
    if (dep[x]<dep[y]) swap(x,y);
    int tmp=dep[x]-dep[y];
    for (int i=19;i>=0;i--)
        if (tmp&bin[i]) x=fa[x][i];
    for (int i=19;i>=0;i--)
        if (fa[x][i]!=fa[y][i])
            x=fa[x][i],y=fa[y][i];
    return (x==y)?x:fa[x][0];
}
void setcolor(int k,int c,int sz){
    memset(t[k].s,0,sizeof(t[k].s));
    t[k].s[c]=sz;
    t[k].tag=c;
}
void pushdown(int k,int l,int r){
    if (!t[k].tag||l==r) return;
    int mid=(l+r)/2;
    setcolor(k*2,t[k].tag,mid-l+1);
    setcolor(k*2+1,t[k].tag,r-mid);
    t[k].tag=0;
}
void build(int k,int l,int r){
    t[k].s[0]=r-l+1;
    if (l==r) return;
    int mid=(l+r)/2;
    build(k*2,l,mid);
    build(k*2+1,mid+1,r);
}
int ask(int k,int l,int r,int x,int y,int c){
    int mid=(l+r)/2,ans;
    pushdown(k,l,r);
    if (l==x&&r==y){
        ans=r-l+1-t[k].s[c];
        setcolor(k,c,r-l+1);
        return ans;
    }
    if (y<=mid) ans=ask(k*2,l,mid,x,y,c);
    else if (x>mid) ans=ask(k*2+1,mid+1,r,x,y,c);
    else ans=ask(k*2,l,mid,x,mid,c)+ask(k*2+1,mid+1,r,mid+1,y,c);
    for (int i=0;i<8;i++) t[k].s[i]=t[k*2].s[i]+t[k*2+1].s[i];
    return ans;
}
int ask(int x,int f,int z){
    int ans=0;
    for (;top[x]!=top[f];x=fa[top[x]][0])
        ans+=ask(1,1,n,pos[top[x]],pos[x],z);
    if (pos[f]+1<=pos[x])
        ans+=ask(1,1,n,pos[f]+1,pos[x],z);
    return ans;
}
int main(){
    bin[0]=1;
    for (int i=1;i<=20;i++)
        bin[i]=bin[i-1]*2;
    scanf("%d",&n);
    for (int i=1;i<n;i++){
        scanf("%d%d",&x,&y);
        add(x,y); add(y,x);
    }
    dfs1(1);
    dfs2(1,1);
    build(1,1,n);
    scanf("%d",&m);
    while (m--){
        scanf("%d%d%d",&x,&y,&z);
        int f=lca(x,y);
        ans[z]+=ask(x,f,z);
        ans[z]+=ask(y,f,z);
    }
    for (int i=1;i<=7;i++)
        printf("%d\n",ans[i]);
}

N=200000万要跑4s
开始大力O（松）优化。
1.加读入优化，-0.5s
2.我们其实i不用记录灰色的信息，因为我们发现他和答案无关。
只要记录7种颜色而非8种。
3.i++改成++i
本机200000要跑3S
可是居然驶过去了？！
目前是本题Rk1 （倒数的）

#include<cmath>
#include<ctime>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define N 200005
using namespace std;
struct edge{int to,next;}e[N*2];
int head[N],sz[N],fa[N][19],dep[N],pos[N],top[N];
int tot,cnt,n,m,x,y,z,bin[25];
struct node{int tag,s[7];}t[N*4];
long long ans[8];
inline int read(){
    int x=0;
    char ch=getchar();
    for (;ch<'0'||ch>'9';ch=getchar());
    for (;ch>='0'&&ch<='9';ch=getchar())
        x=x*10-48+ch;
    return x;
}
void add(int x,int y){
    e[++tot]=(edge){y,head[x]};
    head[x]=tot;
}
void dfs1(int x){
    sz[x]=1;
    for (int i=1;i<=18;++i)
        fa[x][i]=fa[fa[x][i-1]][i-1];
    for (int i=head[x];i;i=e[i].next)
        if (e[i].to!=fa[x][0]){
            dep[e[i].to]=dep[x]+1;
            fa[e[i].to][0]=x;
            dfs1(e[i].to);
            sz[x]+=sz[e[i].to];
        }
}
void dfs2(int x,int tp){
    pos[x]=++cnt; top[x]=tp;
    int k=0;
    for (int i=head[x];i;i=e[i].next)
        if (e[i].to!=fa[x][0]&&sz[e[i].to]>sz[k])
            k=e[i].to;
    if (k) dfs2(k,tp);
    for (int i=head[x];i;i=e[i].next)
        if (e[i].to!=fa[x][0]&&e[i].to!=k)
            dfs2(e[i].to,e[i].to);
}
int lca(int x,int y){
    if (dep[x]<dep[y]) swap(x,y);
    int tmp=dep[x]-dep[y];
    for (int i=18;i>=0;--i)
        if (tmp&bin[i]) x=fa[x][i];
    for (int i=18;i>=0;--i)
        if (fa[x][i]!=fa[y][i])
            x=fa[x][i],y=fa[y][i];
    return (x==y)?x:fa[x][0];
}
void setcolor(int k,int c,int sz){
    memset(t[k].s,0,sizeof(t[k].s));
    t[k].s[c]=sz;
    t[k].tag=c;
}
void pushdown(int k,int l,int r){
    if (t[k].tag==-1) return;
    int mid=(l+r)/2;
    setcolor(k*2,t[k].tag,mid-l+1);
    setcolor(k*2+1,t[k].tag,r-mid);
    t[k].tag=-1;
}
void build(int k,int l,int r){
    t[k].tag=-1;
    if (l==r) return;
    int mid=(l+r)/2;
    build(k*2,l,mid);
    build(k*2+1,mid+1,r);
}
int ask(int k,int l,int r,int x,int y,int c){
    int mid=(l+r)/2,ans;
    if (l==x&&r==y){
        ans=r-l+1-t[k].s[c];
        setcolor(k,c,r-l+1);
        return ans;
    }
    pushdown(k,l,r);
    if (y<=mid) ans=ask(k*2,l,mid,x,y,c);
    else if (x>mid) ans=ask(k*2+1,mid+1,r,x,y,c);
    else ans=ask(k*2,l,mid,x,mid,c)+ask(k*2+1,mid+1,r,mid+1,y,c);
    for (int i=0;i<7;++i) t[k].s[i]=t[k*2].s[i]+t[k*2+1].s[i];
    return ans;
}
int ask(int x,int f,int z){
    int ans=0;
    for (;top[x]!=top[f];x=fa[top[x]][0])
        ans+=ask(1,1,n,pos[top[x]],pos[x],z);
    if (pos[f]+1<=pos[x])
        ans+=ask(1,1,n,pos[f]+1,pos[x],z);
    return ans;
}
int main(){
    bin[0]=1;
    for (int i=1;i<=20;++i)
        bin[i]=bin[i-1]*2;
    n=read();
    for (int i=1;i<n;++i){
        x=read(); y=read();
        add(x,y); add(y,x);
    }
    dfs1(1);
    dfs2(1,1);
    build(1,1,n);
    m=read();
    while (m--){
        x=read(); y=read(); z=read()-1;
        int f=lca(x,y);
        ans[z]+=ask(x,f,z);
        ans[z]+=ask(y,f,z);
    }
    for (int i=0;i<7;i++)
        printf("%d\n",ans[i]);
}