关于CF575B Brides的树剖解法

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
const int N=100005;

int n,k;
int s[10*N];
int u[N],v[N],x[N];

struct node
{
	int nxt;
	int to;
}e[N<<1];
int head[N],tot;

int dep[N],fa[N],sz[N],son[N];
int dfn[N],rnk[N],tg[N],top[N],idx;

int sum1[N<<2],sum2[N<<2];
int tag1[N<<2],tag2[N<<2];
int ans;

inline void read(int &x)
{
	int f=1;char c;
	for(x=0,c=getchar();c<'0'||c>'9';c=getchar()) if(c=='-') f=-1;
	for(;c>='0'&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48); x*=f;
}

inline void add(int from,int to)
{
	e[++tot].to=to;
	e[tot].nxt=head[from];
	head[from]=tot;
}

inline void dfs1(int x)
{
	sz[x]=1;
	son[x]=0;
	for(int i=head[x];i;i=e[i].nxt)
	{
		int v=e[i].to;
		if(v==fa[x]) continue;
		dep[v]=dep[x]+1;
		fa[v]=x;
		dfs1(v);
		sz[x]+=sz[v];
		if(sz[son[x]]<sz[v]) son[x]=v;
	}
	return ;
} 
inline void dfs2(int x,int tp)
{
	dfn[x]=++idx;
	rnk[idx]=x;
	top[x]=tp;
	if(son[x]) dfs2(son[x],tp);
	for(int i=head[x];i;i=e[i].nxt)
	{
		int v=e[i].to;
		if(v==fa[x]||v==son[x]) continue;
		dfs2(v,v);
	}
	return ;
}

inline void pushup(int x)
{
	sum1[x]=(sum1[x<<1]+sum1[x<<1|1])%mod;
	sum2[x]=(sum2[x<<1]+sum2[x<<1|1])%mod;
}
inline void pushdown1(int x)
{
	sum1[x<<1]=1ll*sum1[x<<1]*tag1[x]%mod;
	sum1[x<<1|1]=1ll*sum1[x<<1|1]*tag1[x]%mod;
	
	tag1[x<<1]=1ll*tag1[x<<1]*tag1[x]%mod;
	tag1[x<<1|1]=1ll*tag1[x<<1|1]*tag1[x]%mod;
	

	tag1[x]=1;
	return ;
}
inline void pushdown2(int x)
{
	sum2[x<<1]=sum2[x<<1]*tag2[x]%mod;
	sum2[x<<1|1]=sum2[x<<1|1]*tag2[x]%mod;
	
	tag2[x<<1]=tag2[x<<1]*tag2[x]%mod;
	tag2[x<<1|1]=tag2[x<<1|1]*tag2[x]%mod;
	

	tag2[x]=1;
	return ;
}
inline void build(int x,int l,int r)
{
	tag1[x]=tag2[x]=1;
	if(l==r)
	{
		sum1[x]=sum2[x]=0;
		if(tg[rnk[l]]==-1) sum1[x]=1;
		if(tg[rnk[l]]==1) sum2[x]=1;
		return ;
	}
	int mid=l+r>>1;
	build(x<<1,l,mid);
	build(x<<1|1,mid+1,r);
	pushup(x);return ;
}
inline void update1(int x,int l,int r,int ql,int qr)
{
	if(ql<=l&&r<=qr)
	{
		sum1[x]=2ll*sum1[x]%mod;
		tag1[x]=2ll*tag1[x]%mod;
		return ; 
	}
	int mid=l+r>>1;
	pushdown1(x);
	if(ql<=mid) update1(x<<1,l,mid,ql,qr);
	if(qr>mid) update1(x<<1|1,mid+1,r,ql,qr);
	pushup(x);return ;
}
inline void update2(int x,int l,int r,int ql,int qr)
{
	if(ql<=l&&r<=qr)
	{
		sum2[x]=2ll*sum2[x]%mod;
		tag2[x]=2ll*tag2[x]%mod;
		return ; 
	}
	int mid=l+r>>1;
	pushdown2(x);
	if(ql<=mid) update2(x<<1,l,mid,ql,qr);
	if(qr>mid) update2(x<<1|1,mid+1,r,ql,qr);
	pushup(x);return ;
}
inline int query1(int x,int l,int r,int ql,int qr)
{
	if(ql<=l&&r<=qr) return sum1[x];
	int mid=l+r>>1;
	int rest=0;
	pushdown1(x);
	if(ql<=mid) rest+=query1(x<<1,l,mid,ql,qr);
	if(qr>mid) rest+=query1(x<<1|1,mid+1,r,ql,qr);
	pushup(x);
	return rest%mod;
}
inline int query2(int x,int l,int r,int ql,int qr)
{
	if(ql<=l&&r<=qr) return sum2[x];
	int mid=l+r>>1;
	int rest=0;
	pushdown2(x);
	if(ql<=mid) rest+=query2(x<<1,l,mid,ql,qr);
	if(qr>mid) rest+=query2(x<<1|1,mid+1,r,ql,qr);
	pushup(x);
	return rest%mod;
}

inline int Tquery(int u,int v)
{
	int rest=0;
	while(top[u]!=top[v])
	{
		if(dep[top[u]]>dep[top[v]])
		{
			rest=(rest+query1(1,1,n,dfn[top[u]],dfn[u]))%mod;
			update1(1,1,n,dfn[top[u]],dfn[u]);
			u=fa[top[u]];
		}
		else
		{
			rest=(rest+query2(1,1,n,dfn[top[v]],dfn[v]))%mod;
			update2(1,1,n,dfn[top[v]],dfn[v]);
			v=fa[top[v]];
		}
	}
	if(u==v) return rest;
	if(dep[u]<dep[v]) 
	{
		rest=(rest+query2(1,1,n,dfn[u]+1,dfn[v]))%mod;
		update2(1,1,n,dfn[u]+1,dfn[v]);
	}
	else 
	{	
		rest=(rest+query1(1,1,n,dfn[v]+1,dfn[u]))%mod;
		update1(1,1,n,dfn[v]+1,dfn[u]);
	}
	return rest;
}
int main()
{
	read(n);
	for(int i=1;i<n;i++)
	{
		read(u[i]);read(v[i]);read(x[i]);
		add(u[i],v[i]);
		add(v[i],u[i]);
	}
	read(k);
	for(int i=1;i<=k;i++) read(s[i]);
	dfs1(1);dfs2(1,1);
	for(int i=1;i<n;i++)
	{
		if(!x[i]) continue;
		if(fa[v[i]]==u[i]) tg[v[i]]=-1;
		else tg[u[i]]=1;
	}
//	for(int i=1;i<=n;i++) printf("%d ",tg[i]);
//	puts("");
	build(1,1,n);
	ans=Tquery(1,s[1]);
//	printf("%lld\n",ans);
	for(int i=1;i<k;i++)
	{ 
		ans=(ans+Tquery(s[i],s[i+1]))%mod;
//		printf("%lld\n",ans); 
	}
	printf("%d\n",ans); 
	return 0;
}