White Falcon And Tree
Problem Statement :
White Falcon has a tree with nodes. Each node contains a linear function. Let's denote by the linear function contained in the node .
Let's denote the path from node to node like this: , where and , and and are connected.
White Falcon also has queries. They are in the following format:
. Assign as the function of all the nodes on the path from to , i.e., is changed to where is the path from to .
. Calculate modulo
Input Format
The first line contains , the number of nodes. The following lines each contain two integers and that describe the function .
Following lines contain edges of the tree.
The next line contains , the number of queries. Each subsequent line contains one of the queries described above.
Output Format
For every query of the second kind, print one line containing an integer, the answer for that query.
Constraints
1 <= N <= 50000(Number of nodes)
1 <= Q <= 50000 (Number of queries)
0 <= a, b, x <= 10^9 +7
Solution :
Solution in C :
In C++ :
#include<math.h>
#include<algorithm>
#include<cstdlib>
#include<iostream>
#include<stdio.h>
#include<map>
#include<set>
#include<string>
#include<assert.h>
#include<vector>
#include<ctime>
#include<queue>
#include<deque>
#include<sstream>
#include<stack>
#include<sstream>
#define MA(a,b) ((a)>(b)?(a):(b))
#define MI(a,b) ((a)<(b)?(a):(b))
#define AB(a) (-(a)<(a)?(a):-(a))
#define X first
#define Y second
#define mp make_pair
#define pb push_back
#define pob pop_back
#define ep 0.000001
#define pi 3.1415926535897932384626433832795
#define na(x) ((x)<P?(x):(x)-P)
using namespace std;
const int N=50001;
const long long P=1000000007;
int n,a[N],b[N],x,y,anew,bnew,L,R;
vector <int> v[N];
struct ele {
bool f;
long long fa,fb;
long long a,b,br;
ele *l,*r;
} *tnt,*tnt2;
struct HLT{
vector <int> ind;
ele *start;
inline ele *mk(){
ele *t=(ele*)malloc(sizeof(ele));
t->a=t->b=t->br=0;
t->f=0;
t->l=t->r=NULL;
return t;
}
inline void add(ele *&t,ele *L,ele *R){
t->a=(L->a*R->a)%P;
t->b=(L->b*R->a+R->b)%P;
t->br=(R->br*L->a+L->br)%P;
}
inline void add2(ele *&t,ele *L,ele *R){
t->b=(L->b*R->a+R->b)%P;
t->a=(L->a*R->a)%P;
}
inline void po(ele *&t,int x){
tnt->a=t->fa;
tnt->b=t->fb;
t->a=1;
t->b=0;
while (x){
if (x&1) add2(t,t,tnt);
x>>=1;
add2(tnt,tnt,tnt);
}
t->br=t->b;
}
void bil(int l,int r,ele *&t){
if (t==NULL) t=mk();
if (l+1==r) {
t->a=a[ind[l]];
t->b=t->br=b[ind[l]];
return;
}
bil(l,(l+r)/2,t->l);
bil((l+r)/2,r,t->r);
add(t,t->l,t->r);
}
void up(int l,int r,ele *&t){
if (R<l || r-1<L) return;
if (L<=l && r-1<=R){
t->f=1;
t->fa=anew;
t->fb=bnew;
po(t,r-l);
return;
}
if (t->f){
t->l->fa=t->fa;
t->l->fb=t->fb;
t->l->f=1;
po(t->l,(l+r)/2-l);
t->r->fa=t->fa;
t->r->fb=t->fb;
t->r->f=1;
po(t->r,r-(l+r)/2);
t->f=0;
}
up(l,(l+r)/2,t->l);
up((l+r)/2,r,t->r);
add(t,t->l,t->r);
}
long long calc(int l,int r,ele *t,long long x,bool rev){
if (L<=l && r-1<=R) return (t->a*x+(rev?t->br:t->b))%P;
if (r-1<L || R<l) return x;
if (t->f){
tnt2->fa=t->fa;
tnt2->fb=t->fb;
po(tnt2,MI(R,r-1)-MA(l,L)+1);
return (tnt2->a*x+(rev?tnt2->br:tnt2->b))%P;
}
if ( rev) return calc(l,(l+r)/2,t->l,calc((l+r)/2,r,t->r,x,rev),rev);
if (!rev) return calc((l+r)/2,r,t->r,calc(l,(l+r)/2,t->l,x,rev),rev);
return 0ll;
}
} A[N];
struct mis{
int HLTind,HLTnum,p[16],deep;
} node[N];
int HLTN;
int go(int x,int fr)
{
node[x].deep=node[fr].deep+1;
int S=1;
vector <int> s;
for (int i=0;i<v[x].size();i++) s.pb(v[x][i]!=fr?go(v[x][i],x):0),S+=s[i];
bool fin=0;
for (int i=0;i<v[x].size();i++)
if (S<=s[i]*2){
node[x].HLTind=node[v[x][i]].HLTind;
fin=1;
}
if (fin==0) node[x].HLTind=HLTN,HLTN++;
node[x].HLTnum=A[node[x].HLTind].ind.size();
A[node[x].HLTind].ind.pb(x);
A[node[x].HLTind].start=NULL;
node[x].p[0]=fr;
return S;
}
void up(int x,int upto){
int HLTi=node[x].HLTind;
L=node[x].HLTnum;
if (HLTi==node[upto].HLTind) R=node[upto].HLTnum;
else R=A[HLTi].ind.size()-1;
A[HLTi].up(0,A[HLTi].ind.size(),A[HLTi].start);
if (node[A[HLTi].ind[R]].deep<=node[upto].deep) return;
up(node[A[HLTi].ind[R]].p[0],upto);
}
long long calc(int x,int upto,bool rev,long long RET){
if (node[x].deep<node[upto].deep) return RET;
int HLTi=node[x].HLTind;
L=node[x].HLTnum;
if (HLTi==node[upto].HLTind) R=node[upto].HLTnum;
else R=A[HLTi].ind.size()-1;
if (rev)
if (node[A[HLTi].ind[R]].deep>node[upto].deep)
RET= calc(node[A[HLTi].ind[R]].p[0],upto,rev,RET);
L=node[x].HLTnum;
if (HLTi==node[upto].HLTind) R=node[upto].HLTnum;
else R=A[HLTi].ind.size()-1;
RET=A[HLTi].calc(0,A[HLTi].ind.size(),A[HLTi].start,RET,rev);
if (!rev)
if (node[A[HLTi].ind[R]].deep>node[upto].deep)
RET= calc(node[A[HLTi].ind[R]].p[0],upto,rev,RET);
return RET;
}
int LCA(int x,int y){
for (int i=15;i>=0;i--)
if (node[node[x].p[i]].deep>=node[y].deep) x=node[x].p[i]; else
if (node[node[y].p[i]].deep>=node[x].deep) y=node[y].p[i];
if (x==y) return x;
for (int i=15;i>=0;i--)
if (node[x].p[i]!=node[y].p[i]) x=node[x].p[i],y=node[y].p[i];
return node[x].p[0];
}
int LCAto(int x,int upto){
for (int i=15;i>=0;i--)
if (node[node[x].p[i]].deep>node[upto].deep) x=node[x].p[i];
if (x== upto) return 0;
return x;
}
int main()
{
node[0].deep=P;
tnt=new ele;
tnt2=new ele;
// freopen("text","r",stdin);
scanf("%d",&n);
for (int i=1;i<=n;i++) scanf("%d%d",&a[i],&b[i]);
for (int x,y,i=1;i<n;i++){
scanf("%d%d",&x,&y);
v[x].pb(y);
v[y].pb(x);
}
go(1,1);
for (int j=1;j<16;j++)
for (int i=1;i<=n;i++)
node[i].p[j]=node[node[i].p[j-1]].p[j-1];
for (int i=0;i<HLTN;i++)
A[i].bil(0,(int)A[i].ind.size(),A[i].start);
int query,type,LCAp,startv;
scanf("%d",&query);
while (query--){
scanf("%d",&type);
if (type==1){
scanf("%d%d%d%d",&x,&y,&anew,&bnew);
LCAp=LCA(x,y);
up(x,LCAp);
up(y,LCAp);
}else {
scanf("%d%d%d",&x,&y,&startv);
LCAp=LCA(x,y);
printf("%lld\n",calc(y,LCAto(y,LCAp),1,calc(x,LCAp,0,startv)));
}
}
return 0;
}
In Java :
import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.InputMismatchException;
public class WFAT2 {
static InputStream is;
static PrintWriter out;
static String INPUT = "";
static int mod = 1000000007;
static void solve()
{
int n = ni();
int[][] co = new int[n][];
for(int i = 0;i < n;i++){
co[i] = new int[]{ni(), ni()};
}
int[] from = new int[n-1];
int[] to = new int[n-1];
for(int i = 0;i < n-1;i++){
from[i] = ni()-1;
to[i] = ni()-1;
}
int[][] g = packU(n, from, to);
int[][] pars = parents3(g, 0);
int[] par = pars[0], ord = pars[1], dep = pars[2];
int[] clus = decomposeToHeavyLight(g, par, ord);
int[][] cluspath = clusPaths(clus, ord);
int[] clusiind = clusIInd(cluspath, n);
SegmentTreeNodePlus[] sts =
new SegmentTreeNodePlus[cluspath.length];
for(int i = 0;i < cluspath.length;i++){
int[][] lco = new int[cluspath[i].length][];
for(int j = 0;j < cluspath[i].length;j++){
lco[j] = co[cluspath[i][j]];
}
sts[i] = new SegmentTreeNodePlus(lco);
}
int[][] spar = logstepParents(par);
int Q = ni();
for(int z = 0;z < Q;z++){
int t = ni();
if(t == 1){
int u = ni()-1, v = ni()-1, a = ni(), b = ni();
int lca = lca2(u, v, spar, dep);
int[][] pr = query2(u, lca, v, clus,
cluspath, clusiind, par);
for(int[] e : pr){
sts[e[0]].update(Math.min(e[1], e[2]),
Math.max(e[1], e[2])+1, a, b);
}
}else{
int u = ni()-1, v = ni()-1;
long x = ni();
int lca = lca2(u, v, spar, dep);
int[][] pr = query2(u, lca, v, clus, cluspath, clusiind, par);
for(int[] e : pr){
if(e[1] <= e[2]){
x = sts[e[0]].apply(e[1], e[2]+1, x, false);
}else{
x = sts[e[0]].apply(e[2], e[1]+1, x, true);
}
}
out.println(x);
}
}
}
public static int lca2(int a, int b,
int[][] spar, int[] depth) {
if (depth[a] < depth[b]) {
b = ancestor(b, depth[b] - depth[a], spar);
} else if (depth[a] > depth[b]) {
a = ancestor(a, depth[a] - depth[b], spar);
}
if (a == b)
return a;
int sa = a, sb = b;
for (int low = 0, high = depth[a], t =
Integer.highestOneBit(high), k = Integer
.numberOfTrailingZeros(t); t > 0; t >>>= 1, k--) {
if ((low ^ high) >= t) {
if (spar[k][sa] != spar[k][sb]) {
low |= t;
sa = spar[k][sa];
sb = spar[k][sb];
} else {
high = low | t - 1;
}
}
}
return spar[0][sa];
}
protected static int ancestor(int a, int m, int[][] spar) {
for (int i = 0; m > 0 && a != -1; m >>>= 1, i++) {
if ((m & 1) == 1)
a = spar[i][a];
}
return a;
}
public static int[][] logstepParents(int[] par) {
int n = par.length;
int m = Integer.numberOfTrailingZeros(
Integer.highestOneBit(n - 1)) + 1;
int[][] pars = new int[m][n];
pars[0] = par;
for (int j = 1; j < m; j++) {
for (int i = 0; i < n; i++) {
pars[j][i] = pars[j - 1][i] == -1 ? -1
: pars[j - 1][pars[j - 1][i]];
}
}
return pars;
}
public static class SegmentTreeNodePlus {
public int M, H, N;
public Node[] node;
public int[][] cover;
private static class Node
{
long co;
long lc;
long rc;
public Node() {
co = 1;
lc = rc = 0;
}
public Node(long co, long lc, long rc) {
this.co = co;
this.lc = lc;
this.rc = rc;
}
public long apply(long x, boolean dir)
{
if(!dir){
return (co * x + lc) % mod;
}else{
return (co * x + rc) % mod;
}
}
}
public SegmentTreeNodePlus(int[][] co)
{
N = co.length;
M = Integer.highestOneBit(Math.max(N-1, 1))<<2;
H = M>>>1;
node = new Node[M];
cover = new int[H][];
for(int i = 0;i < N;i++){
node[H+i] = new Node(co[i][0], co[i][1], co[i][1]);
}
for(int i = H-1;i >= 1;i--)propagate(i);
}
private void propagate(int cur)
{
node[cur] = prop2(node[2*cur], node[2*cur+1],
cover[cur], node[cur], H/Integer.highestOneBit(cur));
}
static final int mod = 1000000007;
// ax+b
// cx+d
// c(ax+b)+d=cax+cb+d
// a(cx+d)+b=acx+ad+b
// a(ax+b)+b=a^2*x+ab+b
private Node prop2(Node L, Node R,
int[] cover, Node C, int len)
{
if(L != null && R != null){
if(C == null)C = new Node();
if(cover == null){
C.co = L.co * R.co % mod;
C.lc = (R.co * L.lc + R.lc) % mod;
C.rc = (L.co * R.rc + L.rc) % mod;
}else{
long co = cover[0], c = cover[1];
for(int x = len;x > 1;x >>>= 1){
long nco = co * co % mod;
long nc = (co * c + c) % mod;
co = nco;
c = nc;
}
C.co = co;
C.lc = C.rc = c;
}
return C;
}else if(L != null){
return prop1(L, cover, C, len);
}else if(R != null){
return prop1(R, cover, C, len);
}else{
return null;
}
}
private Node prop1(Node L, int[] cover, Node C, int len)
{
if(C == null)C = new Node();
if(cover == null){
C.co = L.co;
C.lc = L.lc;
C.rc = L.rc;
}else{
long co = cover[0], c = cover[1];
for(int x = len;x > 1;x >>>= 1){
long nco = co * co % mod;
long nc = (co * c + c) % mod;
co = nco;
c = nc;
}
C.co = co;
C.lc = C.rc = c;
}
return C;
}
int[] temp = null;
public void update(int l, int r, int a, int b) {
temp = new int[]{a, b};
if(l < r)update(l, r, a, b, 0, H, 1); }
protected void update(int l, int r, int a,
int b, int cl, int cr, int cur)
{
if(cur >= H){
node[cur].co = a;
node[cur].lc = node[cur].rc = b;
}else if(l <= cl && cr <= r){
cover[cur] = temp;
propagate(cur);
}else{
int mid = cl+cr>>>1;
boolean bp = false;
if(cover[cur] != null){
if(2*cur < H){
cover[2*cur] = cover[cur];
cover[2*cur+1] = cover[cur];
cover[cur] = null;
bp = true;
}else{
node[2*cur].co = cover[cur][0];
node[2*cur].lc = node[2*cur].rc = cover[cur][1];
node[2*cur+1].co = cover[cur][0];
node[2*cur+1].lc = node[2*cur+1].rc = cover[cur][1];
cover[cur] = null;
}
}
if(cl < r && l < mid){
update(l, r, a, b, cl, mid, 2*cur);
}else if(bp){
propagate(2*cur);
}
if(mid < r && l < cr){
update(l, r, a, b, mid, cr, 2*cur+1);
}else if(bp){
propagate(2*cur+1);
}
propagate(cur);
}
}
public long apply(int l, int r, long x, boolean dir) {
return apply(l, r, x, dir, 0, H, 1);
}
protected long apply(int l, int r, long x,
boolean dir, int cl, int cr, int cur)
{
if(l <= cl && cr <= r){
return node[cur].apply(x, dir);
}else{
int mid = cl+cr>>>1;
if(cover[cur] != null){
long co = cover[cur][0], c = cover[cur][1];
for(int h = Math.min(r, cr) - Math.max(l, cl);h > 0;h >>>= 1){
if((h&1) == 1){
x = (co * x + c) % mod;
}
long nco = co * co % mod;
long nc = (co * c + c) % mod;
co = nco;
c = nc;
}
return x;
}
if(!dir){
if(cl < r && l < mid){
x = apply(l, r, x, dir, cl, mid, 2*cur);
}
if(mid < r && l < cr){
x = apply(l, r, x, dir, mid, cr, 2*cur+1);
}
}else{
if(mid < r && l < cr){
x = apply(l, r, x, dir, mid, cr, 2*cur+1);
}
if(cl < r && l < mid){
x = apply(l, r, x, dir, cl, mid, 2*cur);
}
}
return x;
}
}
}
public static int[][] parents3(int[][] g,
int root) {
int n = g.length;
int[] par = new int[n];
Arrays.fill(par, -1);
int[] depth = new int[n];
depth[0] = 0;
int[] q = new int[n];
q[0] = root;
for (int p = 0, r = 1; p < r; p++) {
int cur = q[p];
for (int nex : g[cur]) {
if (par[cur] != nex) {
q[r++] = nex;
par[nex] = cur;
depth[nex] = depth[cur] + 1;
}
}
}
return new int[][] { par, q, depth };
}
public static int[] decomposeToHeavyLight(int[][] g,
int[] par, int[] ord)
{
int n = g.length;
int[] size = new int[n];
Arrays.fill(size, 1);
for(int i = n-1;i > 0;i--)size[par[ord[i]]] += size[ord[i]];
int[] clus = new int[n];
Arrays.fill(clus, -1);
int p = 0;
outer:
for(int i = 0;i < n;i++){
int u = ord[i];
if(clus[u] == -1)clus[u] = p++;
for(int v : g[u]){
if(par[u] != v && size[v] >= size[u]/2){
clus[v] = clus[u];
continue outer;
}
}
for(int v : g[u]){
if(par[u] != v){
clus[v] = clus[u];
break;
}
}
}
return clus;
}
public static int[][] clusPaths(int[] clus, int[] ord)
{
int n = clus.length;
int[] rp = new int[n];
int sup = 0;
for(int i = 0;i < n;i++){
rp[clus[i]]++;
sup = Math.max(sup, clus[i]);
}
sup++;
int[][] row = new int[sup][];
for(int i = 0;i < sup;i++)row[i] = new int[rp[i]];
for(int i = n-1;i >= 0;i--){
row[clus[ord[i]]][--rp[clus[ord[i]]]] = ord[i];
}
return row;
}
public static int[] clusIInd(int[][] clusPath, int n)
{
int[] iind = new int[n];
for(int[] path : clusPath){
for(int i = 0;i < path.length;i++){
iind[path[i]] = i;
}
}
return iind;
}
public static int[][] query2(int x,
int anc, int y, int[] clus, int[][] cluspath,
int[] clusiind, int[] par)
{
int[][] stack = new int[60][];
int sp = 0;
int cx = clus[x]; // ????
int indx = clusiind[x]; // ?????????
while(cx != clus[anc]){
stack[sp++] = new int[]{cx, indx, 0};
int con = par[cluspath[cx][0]];
indx = clusiind[con];
cx = clus[con];
}
stack[sp++] = new int[]{cx, indx, clusiind[anc]};
int top = sp;
int cy = clus[y]; // ????
int indy = clusiind[y]; // ?????????
while(cy != clus[anc]){
stack[sp++] = new int[]{cy, 0, indy};
int con = par[cluspath[cy][0]];
indy = clusiind[con];
cy = clus[con];
}
if(clusiind[anc] < indy){
stack[sp++] = new int[]{cy, clusiind[anc]+1, indy};
}
for(int p = top, q = sp-1;p < q;p++,q--){
int[] dum = stack[p]; stack[p] = stack[q]; stack[q] = dum;
}
return Arrays.copyOf(stack, sp);
}
static int[][] packU(int n, int[] from, int[] to) {
int[][] g = new int[n][];
int[] p = new int[n];
for (int f : from)
p[f]++;
for (int t : to)
p[t]++;
for (int i = 0; i < n; i++)
g[i] = new int[p[i]];
for (int i = 0; i < from.length; i++) {
g[from[i]][--p[from[i]]] = to[i];
g[to[i]][--p[to[i]]] = from[i];
}
return g;
}
public static void main(String[] args) throws Exception
{
long S = System.currentTimeMillis();
is = INPUT.isEmpty() ? System.in :
new ByteArrayInputStream(INPUT.getBytes());
out = new PrintWriter(System.out);
solve();
out.flush();
long G = System.currentTimeMillis();
tr(G-S+"ms");
}
private static boolean eof()
{
if(lenbuf == -1)return true;
int lptr = ptrbuf;
while(lptr < lenbuf)if(!isSpaceChar(inbuf[lptr++]))
return false;
try {
is.mark(1000);
while(true){
int b = is.read();
if(b == -1){
is.reset();
return true;
}else if(!isSpaceChar(b)){
is.reset();
return false;
}
}
} catch (IOException e) {
return true;
}
}
private static byte[] inbuf = new byte[1024];
static int lenbuf = 0, ptrbuf = 0;
private static int readByte()
{
if(lenbuf == -1)throw new InputMismatchException();
if(ptrbuf >= lenbuf){
ptrbuf = 0;
try { lenbuf = is.read(inbuf); }
catch (IOException e)
{ throw new InputMismatchException(); }
if(lenbuf <= 0)return -1;
}
return inbuf[ptrbuf++];
}
private static boolean isSpaceChar(int c)
{ return !(c >= 33 && c <= 126); }
private static int skip()
{ int b; while((b = readByte()) != -1 && isSpaceChar(b));
return b; }
private static double nd()
{ return Double.parseDouble(ns()); }
private static char nc()
{ return (char)skip(); }
private static String ns()
{
int b = skip();
StringBuilder sb = new StringBuilder();
while(!(isSpaceChar(b)))
{ // when nextLine, (isSpaceChar(b) && b != ' ')
sb.appendCodePoint(b);
b = readByte();
}
return sb.toString();
}
private static char[] ns(int n)
{
char[] buf = new char[n];
int b = skip(), p = 0;
while(p < n && !(isSpaceChar(b))){
buf[p++] = (char)b;
b = readByte();
}
return n == p ? buf : Arrays.copyOf(buf, p);
}
private static char[][] nm(int n, int m)
{
char[][] map = new char[n][];
for(int i = 0;i < n;i++)map[i] = ns(m);
return map;
}
private static int[] na(int n)
{
int[] a = new int[n];
for(int i = 0;i < n;i++)a[i] = ni();
return a;
}
private static int ni()
{
int num = 0, b;
boolean minus = false;
while((b = readByte()) != -1 && !(
(b >= '0' && b <= '9') || b == '-'));
if(b == '-'){
minus = true;
b = readByte();
}
while(true){
if(b >= '0' && b <= '9'){
num = num * 10 + (b - '0');
}else{
return minus ? -num : num;
}
b = readByte();
}
}
private static long nl()
{
long num = 0;
int b;
boolean minus = false;
while((b = readByte()) != -1 && !(
(b >= '0' && b <= '9') || b == '-'));
if(b == '-'){
minus = true;
b = readByte();
}
while(true){
if(b >= '0' && b <= '9'){
num = num * 10 + (b - '0');
}else{
return minus ? -num : num;
}
b = readByte();
}
}
private static void tr(Object... o)
{ if(INPUT.length() != 0)
System.out.println(Arrays.deepToString(o)); }
}
In C :
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct _lnode{
int x;
int w;
struct _lnode *next;
} lnode;
typedef struct _tree{
long long sum[2][2];
long long sum1[2][2];
long long offset1;
long long offset2;
} tree;
#define MOD 1000000007
void insert_edge(int x,int y,int w);
void dfs0(int u);
void dfs1(int u,int c);
void preprocess();
int lca(int a,int b);
void sum(int v,int tl,int tr,int l,int r,tree *t,long long ans[][2],int f);
void range_update(int v,int tl,int tr,int pos1,int pos2,long long o1,long long o2,tree *t);
void merge(long long a[][2],long long b[][2],long long ans[][2]);
void push(int v,int tl,int tr,tree *t);
void range_solve(int x,int y,int a,int b);
int min(int x,int y);
int max(int x,int y);
long long solve(int x,int y,int a);
void one(long long*a,int SIZE);
void mul(long long*a,long long*b,int SIZE);
void powm(long long*a,int n,long long*res,int SIZE);
int N,cn,A[100000],B[100000],level[100000],DP[18][100000],subtree_size[100000],special[100000],node_chain[100000],node_idx[100000],chain_head[100000],chain_len[100000]={0};
lnode *table[100000]={0};
tree *chain[100000];
int main(){
int Q,x,y,a,b,i;
scanf("%d",&N);
for(i=0;i<N;i++)
scanf("%d%d",A+i,B+i);
for(i=0;i<N-1;i++){
scanf("%d%d",&x,&y);
insert_edge(x-1,y-1,1);
}
preprocess();
scanf("%d",&Q);
while(Q--){
scanf("%d",&x);
switch(x){
case 1:
scanf("%d%d%d%d",&x,&y,&a,&b);
range_solve(x-1,y-1,a,b);
break;
default:
scanf("%d%d%d",&x,&y,&a);
printf("%lld\n",solve(x-1,y-1,a));
}
}
return 0;
}
void insert_edge(int x,int y,int w){
lnode *t=malloc(sizeof(lnode));
t->x=y;
t->w=w;
t->next=table[x];
table[x]=t;
t=malloc(sizeof(lnode));
t->x=x;
t->w=w;
t->next=table[y];
table[y]=t;
return;
}
void dfs0(int u){
lnode *x;
subtree_size[u]=1;
special[u]=-1;
for(x=table[u];x;x=x->next)
if(x->x!=DP[0][u]){
DP[0][x->x]=u;
level[x->x]=level[u]+1;
dfs0(x->x);
subtree_size[u]+=subtree_size[x->x];
if(special[u]==-1 || subtree_size[x->x]>subtree_size[special[u]])
special[u]=x->x;
}
return;
}
void dfs1(int u,int c){
lnode *x;
node_chain[u]=c;
node_idx[u]=chain_len[c]++;
for(x=table[u];x;x=x->next)
if(x->x!=DP[0][u])
if(x->x==special[u])
dfs1(x->x,c);
else{
chain_head[cn]=x->x;
dfs1(x->x,cn++);
}
return;
}
void preprocess(){
int i,j;
level[0]=0;
DP[0][0]=0;
dfs0(0);
for(i=1;i<18;i++)
for(j=0;j<N;j++)
DP[i][j] = DP[i-1][DP[i-1][j]];
cn=1;
chain_head[0]=0;
dfs1(0,0);
for(i=0;i<cn;i++){
chain[i]=(tree*)malloc(4*chain_len[i]*sizeof(tree));
memset(chain[i],0,4*chain_len[i]*sizeof(tree));
for(j=0;j<4*chain_len[i];j++)
chain[i][j].offset1=chain[i][j].offset2=-1;
}
for(i=0;i<N;i++)
range_update(1,0,chain_len[node_chain[i]]-1,node_idx[i],node_idx[i],A[i],B[i],chain[node_chain[i]]);
return;
}
int lca(int a,int b){
int i;
if(level[a]>level[b]){
i=a;
a=b;
b=i;
}
int d = level[b]-level[a];
for(i=0;i<18;i++)
if(d&(1<<i))
b=DP[i][b];
if(a==b)return a;
for(i=17;i>=0;i--)
if(DP[i][a]!=DP[i][b])
a=DP[i][a],b=DP[i][b];
return DP[0][a];
}
void sum(int v,int tl,int tr,int l,int r,tree *t,long long ans[][2],int f){
long long a[2][2],b[2][2];
push(v,tl,tr,t);
if(l>r){
ans[0][0]=1;
ans[0][1]=0;
ans[1][0]=0;
ans[1][1]=1;
return;
}
if(l==tl && r==tr){
if(f)
memcpy(ans,t[v].sum1,sizeof(t[v].sum1));
else
memcpy(ans,t[v].sum,sizeof(t[v].sum));
return;
}
int tm=(tl+tr)/2;
sum(v*2,tl,tm,l,min(r,tm),t,a,f);
sum(v*2+1,tm+1,tr,max(l,tm+1),r,t,b,f);
if(f)
merge(b,a,ans);
else
merge(a,b,ans);
return;
}
void range_update(int v,int tl,int tr,int pos1,int pos2,long long o1,long long o2,tree *t){
push(v,tl,tr,t);
if(pos2<tl || pos1>tr)
return;
int tm=(tl+tr)/2;
if(pos1<=tl && pos2>=tr){
t[v].offset1=o1;
t[v].offset2=o2;
}
else{
range_update(v*2,tl,tm,pos1,pos2,o1,o2,t);
range_update(v*2+1,tm+1,tr,pos1,pos2,o1,o2,t);
push(v*2,tl,tm,t);
push(v*2+1,tm+1,tr,t);
merge(t[v*2].sum,t[v*2+1].sum,t[v].sum);
merge(t[v*2+1].sum1,t[v*2].sum1,t[v].sum1);
}
return;
}
void merge(long long a[][2],long long b[][2],long long ans[][2]){
ans[0][0]=(a[0][0]*b[0][0]+a[0][1]*b[1][0])%MOD;
ans[0][1]=(a[0][0]*b[0][1]+a[0][1]*b[1][1])%MOD;
ans[1][0]=(a[1][0]*b[0][0]+a[1][1]*b[1][0])%MOD;
ans[1][1]=(a[1][0]*b[0][1]+a[1][1]*b[1][1])%MOD;
return;
}
void push(int v,int tl,int tr,tree *t){
long long a[2][2];
if(t[v].offset1==-1 || t[v].offset2==-1)
return;
a[0][0]=t[v].offset1;
a[0][1]=t[v].offset2;
a[1][0]=0;
a[1][1]=1;
powm(&a[0][0],tr-tl+1,&t[v].sum[0][0],2);
memcpy(t[v].sum1,t[v].sum,sizeof(t[v].sum));
if(tl!=tr){
t[v*2].offset1=t[v*2+1].offset1=t[v].offset1;
t[v*2].offset2=t[v*2+1].offset2=t[v].offset2;
}
t[v].offset1=t[v].offset2=-1;
return;
}
void range_solve(int x,int y,int a,int b){
int ca=lca(x,y);
while(node_chain[x]!=node_chain[ca]){
range_update(1,0,chain_len[node_chain[x]]-1,0,node_idx[x],a,b,chain[node_chain[x]]);
x=DP[0][chain_head[node_chain[x]]];
}
range_update(1,0,chain_len[node_chain[x]]-1,node_idx[ca],node_idx[x],a,b,chain[node_chain[x]]);
while(node_chain[y]!=node_chain[ca]){
range_update(1,0,chain_len[node_chain[y]]-1,0,node_idx[y],a,b,chain[node_chain[y]]);
y=DP[0][chain_head[node_chain[y]]];
}
if(node_idx[y]!=node_idx[ca])
range_update(1,0,chain_len[node_chain[y]]-1,node_idx[ca]+1,node_idx[y],a,b,chain[node_chain[y]]);
return;
}
int min(int x,int y){
return (x<y)?x:y;
}
int max(int x,int y){
return (x>y)?x:y;
}
long long solve(int x,int y,int a){
int ca=lca(x,y);
long long t1[2][2],t2[2][2]={1,0,0,1},t3[2][2],ans[2][2];
while(node_chain[x]!=node_chain[ca]){
sum(1,0,chain_len[node_chain[x]]-1,0,node_idx[x],chain[node_chain[x]],t1,0);
memcpy(t3,t2,sizeof(t2));
merge(t1,t3,t2);
x=DP[0][chain_head[node_chain[x]]];
}
sum(1,0,chain_len[node_chain[x]]-1,node_idx[ca],node_idx[x],chain[node_chain[x]],t1,0);
memcpy(t3,t2,sizeof(t2));
merge(t1,t3,ans);
t2[0][0]=1;
t2[0][1]=0;
t2[1][0]=0;
t2[1][1]=1;
while(node_chain[y]!=node_chain[ca]){
sum(1,0,chain_len[node_chain[y]]-1,0,node_idx[y],chain[node_chain[y]],t1,1);
memcpy(t3,t2,sizeof(t2));
merge(t3,t1,t2);
y=DP[0][chain_head[node_chain[y]]];
}
if(node_idx[y]!=node_idx[ca]){
sum(1,0,chain_len[node_chain[y]]-1,node_idx[ca]+1,node_idx[y],chain[node_chain[y]],t1,1);
memcpy(t3,t2,sizeof(t2));
merge(t3,t1,t2);
}
merge(t2,ans,t1);
return (a*t1[0][0]+t1[0][1])%MOD;
}
void one(long long*a,int SIZE){
int i,j;
for (i = 0; i < SIZE; i++)
for (j = 0; j < SIZE; j++)
a[i*SIZE+j] = (i == j);
return;
}
void mul(long long*a,long long*b,int SIZE){
int i,j,k;
long long res[SIZE][SIZE];
for(i=0;i<SIZE;i++)
for(j=0;j<SIZE;j++)
res[i][j]=0;
for (i = 0; i < SIZE; i++)
for (j = 0; j < SIZE; j++)
for (k = 0; k < SIZE; k++)
res[i][j] = (res[i][j]+a[i*SIZE+k] * b[k*SIZE+j])%MOD;
for (i = 0; i < SIZE; i++)
for (j = 0; j < SIZE; j++)
a[i*SIZE+j] = res[i][j];
return;
}
void powm(long long*a,int n,long long*res,int SIZE){
one(res,SIZE);
while (n > 0) {
if (n % 2 == 0)
{
mul(a, a,SIZE);
n /= 2;
}
else {
mul(res, a,SIZE);
n--;
}
}
}
View More Similar Problems
Tree: Postorder Traversal
Complete the postorder function in the editor below. It received 1 parameter: a pointer to the root of a binary tree. It must print the values in the tree's postorder traversal as a single line of space-separated values. Input Format Our test code passes the root node of a binary tree to the postorder function. Constraints 1 <= Nodes in the tree <= 500 Output Format Print the
View Solution →Tree: Inorder Traversal
In this challenge, you are required to implement inorder traversal of a tree. Complete the inorder function in your editor below, which has 1 parameter: a pointer to the root of a binary tree. It must print the values in the tree's inorder traversal as a single line of space-separated values. Input Format Our hidden tester code passes the root node of a binary tree to your $inOrder* func
View Solution →Tree: Height of a Binary Tree
The height of a binary tree is the number of edges between the tree's root and its furthest leaf. For example, the following binary tree is of height : image Function Description Complete the getHeight or height function in the editor. It must return the height of a binary tree as an integer. getHeight or height has the following parameter(s): root: a reference to the root of a binary
View Solution →Tree : Top View
Given a pointer to the root of a binary tree, print the top view of the binary tree. The tree as seen from the top the nodes, is called the top view of the tree. For example : 1 \ 2 \ 5 / \ 3 6 \ 4 Top View : 1 -> 2 -> 5 -> 6 Complete the function topView and print the resulting values on a single line separated by space.
View Solution →Tree: Level Order Traversal
Given a pointer to the root of a binary tree, you need to print the level order traversal of this tree. In level-order traversal, nodes are visited level by level from left to right. Complete the function levelOrder and print the values in a single line separated by a space. For example: 1 \ 2 \ 5 / \ 3 6 \ 4 F
View Solution →Binary Search Tree : Insertion
You are given a pointer to the root of a binary search tree and values to be inserted into the tree. Insert the values into their appropriate position in the binary search tree and return the root of the updated binary tree. You just have to complete the function. Input Format You are given a function, Node * insert (Node * root ,int data) { } Constraints No. of nodes in the tree <
View Solution →