usaco 2011 Dec Gold(Grass Planting-树链剖分第一题) (二)
r(i,n) for(int i=1;i<=n;i++)
#define Rep(i,n) for(int i=0;i=0;i--)
#define MEM(a) memset(a,0,sizeof(a))
#define MEMI(a) memset(a,127,sizeof(a))
#define MEMi(a) memset(a,128,sizeof(a))
#define INF (2139062143)
#define F (1000000009)
#define MAXN (100000+10)
#define MAXM (200000+10)
typedef long long ll;
ll n,m;
int edge[MAXN],pre[MAXN]={0},next[MAXN]={0},weight[MAXN]={0},size=1;
void addedge(int u,int v)
{
edge[++size]=v;
next[size]=pre[u];
pre[u]=size;
}
void addedge2(int u,int v){addedge(u,v),addedge(v,u);}
struct node
{
int ch[2],s,mark;
node():s(0),mark(0){ch[0]=ch[1]=0;}
}q[MAXN*10];
int root[MAXN]={0},tail=0;
void pushdown(int x,int l,int r)
{
if (l==r||q[x].mark==0) {q[x].mark=0; return;}
if (!q[x].ch[0]) q[x].ch[0]=++tail;
if (!q[x].ch[1]) q[x].ch[1]=++tail;
int m=l+r>>1,c=q[x].mark;
q[x].mark=0;
q[q[x].ch[0]].mark+=c;q[q[x].ch[0]].s+=c*(m-l+1);
q[q[x].ch[1]].mark+=c;q[q[x].ch[1]].s+=c*(r-m-1+1);
}
void ins(int &x,int l,int r,int L,int R,int c)
{
if (!x) x=++tail;//pushdown(x,l,r);
q[x].s+=c*(min(r,R)-max(L,l)+1);
if (L<=l&&r<=R) {q[x].mark+=c;return;}
int m=l+r>>1;
if (L<=m) ins(q[x].ch[0],l,m,L,R,c);
if (m+1<=R) ins(q[x].ch[1],m+1,r,L,R,c);
}
int find(int x,int l,int r,int L,int R)
{
if (!x) return 0;
pushdown(x,l,r);
if (L<=l&&r<=R) return q[x].s;
int ans=0,m=l+r>>1;
if (L<=m) ans+=find(q[x].ch[0],l,m,L,R);
if (m
tmp) son[x]=v,tmp=siz[v];
}
}
}
void dfs2(int x,int f)
{
if (!top[x]) top[x]=x;
if (son[x]) top[son[x]]=top[x];
Forp(x)
{
int &v=edge[p];
if (v^f)
{
dfs2(v,x);
w[v]=p;
}
}
}
void inc(int u,int v)
{
while(top[u]^top[v])
{
int fu=top[u],fv=top[v];
if (dep[fu]dep[fu]) ins(root[fu],1,n-1,1,dep[u]-dep[fu],1);
u=fu;
if (w[u]) weight[w[u]]++;u=fa[u];
}
if (dep[u]dep[fu]) ans+=find(root[fu],1,n-1,1,dep[u]-dep[fu]);
u=fu;
if (w[u]) ans+=weight[w[u]];u=fa[u];
}
if (dep[u]