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
Sparse Arrays
There is a collection of input strings and a collection of query strings. For each query string, determine how many times it occurs in the list of input strings. Return an array of the results. Example: strings=['ab', 'ab', 'abc'] queries=['ab', 'abc', 'bc'] There are instances of 'ab', 1 of 'abc' and 0 of 'bc'. For each query, add an element to the return array, results=[2,1,0]. Fun
View Solution →Array Manipulation
Starting with a 1-indexed array of zeros and a list of operations, for each operation add a value to each of the array element between two given indices, inclusive. Once all operations have been performed, return the maximum value in the array. Example: n=10 queries=[[1,5,3], [4,8,7], [6,9,1]] Queries are interpreted as follows: a b k 1 5 3 4 8 7 6 9 1 Add the valu
View Solution →Print the Elements of a Linked List
This is an to practice traversing a linked list. Given a pointer to the head node of a linked list, print each node's data element, one per line. If the head pointer is null (indicating the list is empty), there is nothing to print. Function Description: Complete the printLinkedList function in the editor below. printLinkedList has the following parameter(s): 1.SinglyLinkedListNode
View Solution →Insert a Node at the Tail of a Linked List
You are given the pointer to the head node of a linked list and an integer to add to the list. Create a new node with the given integer. Insert this node at the tail of the linked list and return the head node of the linked list formed after inserting this new node. The given head pointer may be null, meaning that the initial list is empty. Input Format: You have to complete the SinglyLink
View Solution →Insert a Node at the head of a Linked List
Given a pointer to the head of a linked list, insert a new node before the head. The next value in the new node should point to head and the data value should be replaced with a given value. Return a reference to the new head of the list. The head pointer given may be null meaning that the initial list is empty. Function Description: Complete the function insertNodeAtHead in the editor below
View Solution →Insert a node at a specific position in a linked list
Given the pointer to the head node of a linked list and an integer to insert at a certain position, create a new node with the given integer as its data attribute, insert this node at the desired position and return the head node. A position of 0 indicates head, a position of 1 indicates one node away from the head and so on. The head pointer given may be null meaning that the initial list is e
View Solution →