总觉得之前是非正解

这个写出来以后发现..更非正解..

题意:http://absi2011.is-programmer.com/posts/202346.html

记b(i)表示到i到根的路径的权值和..

每次修改就是一段区间的修改..

然后..我们就可以愉快的玩差分了...

然后分块处理..复杂度是[tex]O(kq + q\sqrt{n})[/tex]的

但是..不知道为啥跑得比之前那个慢多了..

不管了..就这样吧

代码:

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<math.h>
#include<string>
#include<time.h>
#include<bitset>
#include<vector>
#include<memory>
#include<utility>
#include<stdio.h>
#include<sstream>
#include<fstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
struct edge
{
    int y;
    edge * next;
};
edge * li[500005];
edge * new_edge()
{
    static edge a[1000005];
    static int top=0;
    return &a[top++];
}
void inserts(int x,int y)
{
    edge * t=new_edge();
    t->y=y;
    t->next=li[x];
    li[x]=t;
}
void insert_edge(int x,int y)
{
    inserts(x,y);
    inserts(y,x);
}
int dfn[500005];
long long a[500005];
long long sum[500005];
int block=735;
int father[500005];
int depth[500005];
int size[500005];
long long b[500005];
void dfs(int x)
{
    static int now=0;
    dfn[x]=now++;
    edge * t;
    size[x]=1;
    for (t=li[x];t!=0;t=t->next)
    {
        if (t->y==father[x]) continue;
        father[t->y]=x;
        depth[t->y]=depth[x]+1;
        dfs(t->y);
        size[x]+=size[t->y];
    }
}
int n;
int up[500005][25];
void get_lca()
{
    int i;
    for (i=0;i<n;i++)
    {
        up[i][0]=father[i];
    }
    for (i=1;i<20;i++)
    {
        int j;
        for (j=0;j<n;j++)
        {
            if (up[j][i-1]==-1)
            {
                up[j][i]=-1;
            }
            else
            {
                up[j][i]=up[up[j][i-1]][i-1];
            }
        }
    }
}
int lca(int x,int y)
{
    if (depth[x]<depth[y]) swap(x,y);
    int t=depth[x]-depth[y];
    int i;
    for (i=19;i>=0;i--)
    {
        if ((1<<i)&t) x=up[x][i];
    }
    if (x==y) return x;
    for (i=19;i>=0;i--)
    {
        if (up[x][i]==up[y][i]) continue;
        x=up[x][i];
        y=up[y][i];
    }
    return father[x];
}
long long calc_ans(int x)
{
    int i=0;
    long long ans=0;
    int j=0;
    for (;;)
    {
        i+=block;
        if (i>x) break;
        ans+=sum[j];
        j++;
    }
    i-=block;
    for (;i<=x;i++) ans+=a[i];
    return ans;
}
int main()
{
    #ifdef absi2011
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    ios::sync_with_stdio(false);
    scanf("%d",&n);
    int i;
    for (i=1;i<n;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        insert_edge(x,y);
    }
    father[0]=0;
    depth[0]=0;
    dfs(0);
    get_lca();
    for (i=0;i<n;i++)
    {
        int x;
        scanf("%d",&x);
        b[i]=x;
        a[dfn[i]]=x;
        sum[dfn[i]/block]+=x;
        a[dfn[i]+size[i]]-=x;
        sum[(dfn[i]+size[i])/block]-=x;
    }
    int m;
    scanf("%d",&m);
    for (i=0;i<m;i++)
    {
        int k;
        scanf("%d",&k);
        int j;
        int x1,y1,aa,bb,cc,dd;
        scanf("%d%d%d%d%d%d",&x1,&y1,&aa,&bb,&cc,&dd);
        for (j=0;j<k;j++)
        {
            if (x1<n)
            {
                b[x1]+=y1;
                a[dfn[x1]]+=y1;
                sum[dfn[x1]/block]+=y1;
                a[dfn[x1]+size[x1]]-=y1;
                sum[(dfn[x1]+size[x1])/block]-=y1;
            }
            x1=((long long)x1*aa+bb)%n;
            y1=((long long)y1*cc+dd)%1000000007;
        }
        long long ans=0;
        int x,y;
        scanf("%d%d",&x,&y);
        ans=calc_ans(dfn[x])+calc_ans(dfn[y])-2*calc_ans(dfn[lca(x,y)])+b[lca(x,y)];
        cout<<ans<<'\n';
    }
    return 0;
}