noip 2016 Day 1 T 2:毎日走るのが好き(Lca+樹上差分)

タイトルの説明
cさんはランニングがとても面白いと思って、「毎日走るのが好き」というゲームを作ることにしました.《毎日走るのが好きです》は1つの育成类のゲームで、プレーヤーが毎日时间通りにオンラインになって、カードを打つ任务を完成する必要があります.
このゲームの地図は、1本のノードとエッジを含む木と見なすことができ、各エッジが2つのノードを接続し、任意の2つのノードが1つのパスで互いに達することができる.ツリー上のノード番号は、からの連続正の整数です.
今、プレイヤーがいます.最初のプレイヤーの起点は、終点は.毎日カードを打つ任務が始まる時、すべてのプレーヤーは秒目に同時に自分の起点から出発して、毎秒1本の辺の速度を走って、絶えず最短の経路に沿って自分の終点に向かって走って、終点に着いた後にそのプレーヤーはカードを打つ任務を完成しました.(地図は木なので、一人一人の経路は唯一です)
Cちゃんはゲームの活躍度が知りたくて、ノードごとにオブザーバーが置かれていました.ノードのオブザーバーは秒目にプレイヤーを観察することを選択し、1人のプレイヤーがこのオブザーバーに観察され、そのプレイヤーが秒目にもノードに到着したときだけを観察することができる.Cさんはオブザーバー一人一人が何人観察するか知りたいです.
注意:あるプレイヤーが自分のゴールに着いたら、そのプレイヤーはゲームを終了すると思います.彼はしばらく待ってからオブザーバーに観察されることはできません.すなわち、ノードを終点とするプレイヤーに対して、彼が秒目に再び終点に到着すると、ノードのオブザーバーはそのプレイヤーを観察できない.彼がちょうど秒目にゴールに着いたら、ノードのオブザーバーはこのプレイヤーを観察することができます.
にゅうしゅつりょくけいしき
入力形式:
最初の行には2つの整数和があります.このうち代表木のノード数は,同時にオブザーバーの数であり,プレイヤーの数を代表する.
次の行の各行の2つの整数和は、ノードからノードにエッジがあることを示します.
次の行の整数です.最初の整数は、ノードにオブザーバーが現れる時間を表します.
次の行は、行ごとに2つの整数と、1人のプレイヤーの起点と終点を表します.
すべてのデータに対して、保証します.
出力フォーマット:
1行目の整数を出力し、1番目の整数はノードのオブザーバーがどれだけの人を観察できるかを示します.
入出力サンプル
サンプル#1を入力:
6 3
2 3
1 2
1 4
4 5
4 6
0 2 5 1 2 3
1 5
1 3
2 6
出力サンプル#1:
2 0 0 1 1 1
サンプル#2を入力:
5 3
1 2
2 3
2 4
1 5
0 1 0 3 0
3 1
1 4
5 5
出力サンプル#2:
1 2 1 0 1
テーマ分析:本題の経路は2つのセグメントに分割することができる:u->lca(u,v)とlca(u,v)->v.u->lca(u,v)上の点iの場合、dep[i]+w[i](=A[i])=dep[u]の場合、iの答えが更新され、lca(u,v)->v上の点jの場合、dep[j]-w[j](=dep[v]-len(u,v)の場合、jの答えが更新されます.したがって、uのノードのAにdep[u]の値を付け、fa[lca(u,v)]に削除し、vノードのBにdep[v]-len(u,v)の値を付け、lca(u,v)に削除する.(これによりlca(u,v)が計算や漏れ計を繰り返さないことが保証される).
A配列のみを考慮する.各iについて、そのサブツリーにA[i]のタグ値がどれだけあるかを迅速に知る必要がある.グローバル変数cntA配列を維持し、DFS(i)に入るときにA[i]の個数を記録することができます.これは他の場所で値がA[i]の個数で、点iのタグを加え、Dfsサブツリーで、終了時に個数を確認します.彼らの差は、そのサブツリーで値がA[i]の個数です.Bも同様に処理できますが、負の数である可能性があるのでオフセット量を加算します.時間複雑度O(n*log(n)).
CODE:

#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;

const int maxn=300100;
const int maxl=20;

struct data
{
	int obj,_Next;
} e[maxn<<1];
int head[maxn];
int cur=-1;

struct data1
{
	int obj1,_Next1,id,idx;
} e1[maxn<<2];
int head1[maxn];
int cur1=-1;

int fa[maxn][maxl];
int dep[maxn];

int A[maxn];
int B[maxn];

int cntA[maxn];
int cntB[maxn<<1];

int ans[maxn];
int n,m;

void Add(int x,int y)
{
	cur++;
	e[cur].obj=y;
	e[cur]._Next=head[x];
	head[x]=cur;
}

void Dfs1(int node)
{
	int p=head[node];
	while (p!=-1)
	{
		int son=e[p].obj;
		if (son!=fa[node][0])
		{
			dep[son]=dep[node]+1;
			fa[son][0]=node;
			Dfs1(son);
		}
		p=e[p]._Next;
	}
}

void Make_fa()
{
	for (int j=1; j=0; j--)
		if (dep[fa[u][j]]>=dep[v])
			u=fa[u][j];
	if (u==v) return u;
	for (int j=maxl-1; j>=0; j--)
		if (fa[u][j]!=fa[v][j])
		{
			u=fa[u][j];
			v=fa[v][j];
		}
	return fa[u][0];
}

void Add1(int x,int v,int nid,int nidx)
{
	cur1++;
	e1[cur1].obj1=v;
	e1[cur1].id=nid;
	e1[cur1].idx=nidx;
	e1[cur1]._Next1=head1[x];
	head1[x]=cur1;
}

void Dfs2(int node)
{
	int la=cntA[A[node]];
	int lb=cntB[B[node]+maxn];
	
	int p=head1[node];
	while (p!=-1)
	{
		int v=e1[p].obj1;
		int nid=e1[p].id;
		int nidx=e1[p].idx;
		if (nidx==1) cntA[v]+=nid;
		else cntB[v+maxn]+=nid;
		p=e1[p]._Next1;
	}
	
	p=head[node];
	while (p!=-1)
	{
		int son=e[p].obj;
		if (son!=fa[node][0])
			Dfs2(son);
		p=e[p]._Next;
	}
	
	int na=cntA[A[node]];
	int nb=cntB[B[node]+maxn];
	ans[node]=(na-la)+(nb-lb);
}

int main()
{
	freopen("c.in","r",stdin);
	freopen("c.out","w",stdout);
	
	scanf("%d%d",&n,&m);
	for (int i=0; i<=n; i++) head[i]=-1;
	for (int i=1; i