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
Array Pairs
Consider an array of n integers, A = [ a1, a2, . . . . an] . Find and print the total number of (i , j) pairs such that ai * aj <= max(ai, ai+1, . . . aj) where i < j. Input Format The first line contains an integer, n , denoting the number of elements in the array. The second line consists of n space-separated integers describing the respective values of a1, a2 , . . . an .
View Solution →Self Balancing Tree
An AVL tree (Georgy Adelson-Velsky and Landis' tree, named after the inventors) is a self-balancing binary search tree. In an AVL tree, the heights of the two child subtrees of any node differ by at most one; if at any time they differ by more than one, rebalancing is done to restore this property. We define balance factor for each node as : balanceFactor = height(left subtree) - height(righ
View Solution →Array and simple queries
Given two numbers N and M. N indicates the number of elements in the array A[](1-indexed) and M indicates number of queries. You need to perform two types of queries on the array A[] . You are given queries. Queries can be of two types, type 1 and type 2. Type 1 queries are represented as 1 i j : Modify the given array by removing elements from i to j and adding them to the front. Ty
View Solution →Median Updates
The median M of numbers is defined as the middle number after sorting them in order if M is odd. Or it is the average of the middle two numbers if M is even. You start with an empty number list. Then, you can add numbers to the list, or remove existing numbers from it. After each add or remove operation, output the median. Input: The first line is an integer, N , that indicates the number o
View Solution →Maximum Element
You have an empty sequence, and you will be given N queries. Each query is one of these three types: 1 x -Push the element x into the stack. 2 -Delete the element present at the top of the stack. 3 -Print the maximum element in the stack. Input Format The first line of input contains an integer, N . The next N lines each contain an above mentioned query. (It is guaranteed that each
View Solution →Balanced Brackets
A bracket is considered to be any one of the following characters: (, ), {, }, [, or ]. Two brackets are considered to be a matched pair if the an opening bracket (i.e., (, [, or {) occurs to the left of a closing bracket (i.e., ), ], or }) of the exact same type. There are three types of matched pairs of brackets: [], {}, and (). A matching pair of brackets is not balanced if the set of bra
View Solution →