Problem: tolls (2017 finals)

A group of **N** Foxen reside in a peaceful forest community. Each Fox's
property consists of a tree stump as well as an underground den. There are
**N** \- 1 two-way paths on the ground running amongst the tree stumps, with
the _i_th path connecting the stumps belonging to two different Foxen **Ai**
and **Bi**, such that all **N** stumps can be reached from one another by
following a sequence of paths. Similarly, there are **N** \- 1 underground
tunnels running amongst the dens, with the _i_th tunnel connecting the dens
belonging to Foxen **Ci** and **Di**, such that all **N** dens can be reached
from one another. There's additionally a passageway connecting the tree stump
and den belonging to the 1st Fox, which is the only way in the whole forest to
get underground from the surface and vice versa.

At night the Foxen sleep in their dens, but during the daytime, they like to
emerge and relax lazily on their tree stumps. Each day, every Fox takes a trip
from their den to their tree stump, taking the unique shortest path through
the system of tunnels and paths to get there. However, this often requires
passing through other Foxen's properties, which they don't appreciate a whole
lot. To compensate, the Foxen have started charging each other tolls for said
passage. They don't have much of a currency, but Foxen do love crackers, so
those will do. Over a given period of **M** days, on the _i_th day, two
different Foxen **Wi** and **Xi** will each charge tolls for one of their
pieces of property. If **Yi** = "T", then Fox **Wi** will be charging tolls
for passage through their tree stump. Otherwise, if **Yi** = "D", then Fox
**Wi** will instead be charging tolls for passage through their den.
Similarly, Fox **Xi** will be charging tolls for passage through either their
tree stump (if **Zi**= "T") or their den (if **Zi**= "D").

Each day, whenever a Fox passes through another Fox's den or stump which is
subject to tolls on that day, they'll normally need to pay up with 2 crackers.
However, if they've already paid a toll earlier on that same trip, then the
property-owning Fox will take pity and only charge them 1 cracker instead of
2. As such, a Fox's daily trip may end up costing them at most 3 crackers. A
Fox will never charge themselves a toll, of course. If a pair of Foxen both
owe each other crackers, they'll still both pay up as normal, rather than
attempting to minimize the number of cracker transactions performed.

The Foxen are having some trouble keeping track of how many crackers they owe
one another. On each of the **M** days, they'd like to count up the total
number of crackers which will be charged as part of the tolls for the **N**
trips taken on that day. To avoid dealing with too many large numbers, they'd
like to combine these **M** cracker counts into a single value as follows
(where **Vi** is the _i_th day's count):

( ... (((**V1** * 12,345) + **V2**) * 12,345 + **V3**) ... * 12,345 + **VM**)
modulo 1,000,000,007

Please help the Foxen compute this combined value!

### Input

Input begins with an integer **T**, the number of different communities of
Foxen. For each community of Foxen, there is first a line containing the
space-separated integers **N** and **M**. Then **N - 1** lines follow, the
_i_th of which contains the space-separated integers **Ai** and **Bi**. Then
**N - 1** lines follow, the _i_th of which contains the space-separated
integers **Ci** and **Di**. Then **M** lines follow, the _i_th of which
contains the integers **Wi** and **Xi** and the characters **Yi** and **Zi**,
all separated by spaces.

### Output

For the _i_th community of Foxen, print a line containing "Case #**i**: "
followed by a single integer, the requested combined value based on the **M**
days' cracker counts, modulo 1,000,000,007.

### Constraints

1 ≤ **T** ≤ 30  
2 ≤ **N** ≤ 500,000  
1 ≤ **M** ≤ 500,000  
1 ≤ **Ai**, **Bi**, **Ci**, **Di**, **Wi**, **Xi** ≤ **N**  
Both the sum of **N** values and the sum of **M** values across all **T**
cases do not exceed 1,500,000.

### Explanation of Sample

In the first case, Fox 1 doesn't need to pay any tolls to get from its den to
its tree stump, while Fox 2 must pay 2 crackers to complete its trip due to
passing through Fox's 1 tree stump.

In the second case, 5 crackers will be charged on the first day (the 3 Foxen
must pay 0, 2, and 3 crackers, respectively), 2 crackers will be charged on
the second day, and none will be charged on the third day. This results in a
final answer of (((5 * 12,345) + 2) * 12,345) + 0) modulo 1,000,000,007 =
762,019,815.

In the third case, 7, 6, and 4 crackers will be charged on each of the three
days, respectively.



Sample input:

Sample output:


Code: // Hacker Cup 2017
// Final Round
// Fox Tolls
// Jacob Plachta

#include <algorithm>
#include <functional>
#include <numeric>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <complex>
#include <cstdlib>
#include <ctime>
#include <cstring>
#include <cassert>
#include <string>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <sstream>
using namespace std;

#define LL long long
#define LD long double
#define PR pair<int,int>

#define Fox(i,n) for (i=0; i<n; i++)
#define Fox1(i,n) for (i=1; i<=n; i++)
#define FoxI(i,a,b) for (i=a; i<=b; i++)
#define FoxR(i,n) for (i=(n)-1; i>=0; i--)
#define FoxR1(i,n) for (i=n; i>0; i--)
#define FoxRI(i,a,b) for (i=b; i>=a; i--)
#define Foxen(i,s) for (i=s.begin(); i!=s.end(); i++)
#define Min(a,b) a=min(a,b)
#define Max(a,b) a=max(a,b)
#define Sz(s) int((s).size())
#define All(s) (s).begin(),(s).end()
#define Fill(s,v) memset(s,v,sizeof(s))
#define pb push_back
#define mp make_pair
#define x first
#define y second

template<typename T> T Abs(T x) { return(x<0 ? -x : x); }
template<typename T> T Sqr(T x) { return(x*x); }

const int INF = (int)1e9;
const LD EPS = 1e-12;
const LD PI = acos(-1.0);

bool Read(int &x)
{
	char c,r=0,n=0;
	x=0;
		for(;;)
		{
			c=getchar();
				if ((c<0) && (!r))
					return(0);
				if ((c=='-') && (!r))
					n=1;
				else
				if ((c>='0') && (c<='9'))
					x=x*10+c-'0',r=1;
				else
				if (r)
					break;
		}
		if (n)
			x=-x;
	return(1);
}

#define LIM 500000
#define LIM2 2100000
#define MOD 1000000007

int ind;
int L[2][LIM],R[2][LIM],S[2][LIM];
vector<int> con[LIM];

int sz;
vector<int> lst[LIM2];

void rec(int z,int i,int p)
{
	int j,k;
	L[z][i]=ind++;
		Fox(j,Sz(con[i]))
			if ((k=con[i][j])!=p)
				rec(z,k,i);
	R[z][i]=ind-1;
	S[z][i]=R[z][i]-L[z][i];
}

int Query(int i,int r1,int r2,int a,int b,int v1,int v2)
{
		if ((a<=r1) && (r2<=b))
		{
			return(
				lower_bound(lst[i].begin(),lst[i].end(),v2+1) -
				lower_bound(lst[i].begin(),lst[i].end(),v1)
			);
		}
	i<<=1;
	int m=(r1+r2)>>1,s=0;
		if (a<=m)
			s+=Query(i,r1,m,a,b,v1,v2);
		if (b>m)
			s+=Query(i+1,m+1,r2,a,b,v1,v2);
	return(s);
}

int main()
{
	// vars
	int T,t;
	int N,M;
	int i,j,k,a,b,z,z1,z2;
	int ans,tot;
	char c1,c2;
	// testcase loop
	Read(T);
		Fox1(t,T)
		{
			// input
			Read(N),Read(M);
				Fox(z,2)
				{
					// clear graph
						Fox(i,N)
							con[i].clear();
					// input tree
						Fox(i,N-1)
						{
							Read(j),Read(k),j--,k--;
							con[j].pb(k);
							con[k].pb(j);
						}
					// calculate DFS ordering for this tree
					ind=0;
					rec(z,0,0);
				}
			// construct segment tree
				for(sz=1;sz<N;sz<<=1);
				Fox(i,sz<<1)
					lst[i].clear();
				Fox(i,N)
					lst[sz+L[0][i]].pb(L[1][i]);
				FoxR1(i,sz-1)
				{
					j=i<<1,k=j+1;
					a=b=0;
						while ((a<Sz(lst[j])) && (b<Sz(lst[k])))
							if (lst[j][a]<lst[k][b])
								lst[i].pb(lst[j][a++]);
							else
								lst[i].pb(lst[k][b++]);
						while (a<Sz(lst[j]))
							lst[i].pb(lst[j][a++]);
						while (b<Sz(lst[k]))
							lst[i].pb(lst[k][b++]);
				}
			// handle days
			tot=0;
				while (M--)
				{
					// input
					Read(i),Read(j),i--,j--;
					scanf("%c %c",&c1,&c2);
					z1=c1=='T' ? 0 : 1;
					z2=c2=='T' ? 0 : 1;
					// same tree?
						if (z1==z2)
						{
							z=z1;
								if (L[z][i]>L[z][j])
									swap(i,j);
							// nested subtrees?
								if (L[z][j]<=R[z][i])
								{
									ans=2*S[z][i] + S[z][j];
									goto Done;
								}
							// disjoint subtrees
							ans=2*(S[z][i] + S[z][j]);
							goto Done;
						}
					// different trees
						if (z1)
							swap(i,j);
					ans=2*(S[0][i] + S[1][j]);
						if ((S[0][i]) && (S[1][j]))
							ans-=Query(1,0,sz-1,L[0][i]+1,R[0][i],L[1][j]+1,R[1][j]);
					// update total
Done:;
					tot=((LL)tot*12345+ans)%MOD;
				}
			//output
			printf("Case #%d: %d\n",t,tot);
		}
	return(0);
}