这一题题意:

给你n个点的一颗树(n<=500000)

一共有q次询问,每次询问要你完成k次修改以后,进行一个查询(q<=50000 k<=1000)

问[u,v]以及它们的路径上的所有的点的权值和

k次修改是读入后随机生成的,具体来说是这样的

输入[tex]x_1,y_1,A,B,C,D[/tex]

对于x>=2,我们有

[tex]x_i = (x_{i-1} * A + B)\ mod\ N[/tex]

[tex]y_i = (y_{i-1} * C + D)\ mod\ 10^9+7[/tex]

然后把第[tex]x_i[/tex]个点的权值加上[tex]y_i[tex]

时限8s

直接树链剖分剖分一下

用树状数组代替线段树来维护这个树链剖分

复杂度是[tex]O(k*q \log n+n \log^2 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;
int a[500005];
int n;
long long c[500005];
inline void change(int x,int val)
{
    x++;
    for (;;)
    {
        c[x]+=val;
        x+=(-x)&x;
        if (x>n) return;
    }
}
inline long long queries(int x)
{
    long long sum=0;
    for (;;)
    {
        if (x==0) return sum;
        sum+=c[x];
        x^=(-x)&x;
    }
}
inline long long query(int l,int r)
{
    return queries(r+1)-queries(l);
}
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 father[500005];
int dfn[500005];
int depth[500005];
int vis[500005];
int size[500005];
edge * prefer_child[500005];
int up[500005];
void dfs1(int x)
{
    edge * t;
    size[x]=1;
    prefer_child[x]=0;
    int max_size=0;
    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;
        dfs1(t->y);
        size[x]+=size[t->y];
        if (size[t->y]>max_size)
        {
            max_size=size[t->y];
            prefer_child[x]=t;
        }
    }
}
void dfs2(int x)
{
    static int num=0;
    dfn[x]=num;
    vis[num]=x;
    num++;
    if (prefer_child[x]==0) return;
    up[prefer_child[x]->y]=up[x];
    dfs2(prefer_child[x]->y);
    edge * t;
    for (t=li[x];t!=0;t=t->next)
    {
        if (t->y==father[x]) continue;
        if (t==prefer_child[x]) continue;
        up[t->y]=t->y;
        dfs2(t->y);
    }
}
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]=-1;
    depth[0]=0;
    dfs1(0);
    up[0]=0;
    dfs2(0);
    for (i=0;i<n;i++)
    {
        scanf("%d",&a[i]);
    }
    for (i=1;i<=n;i++)
    {
        c[i]+=a[vis[i-1]];
        int j=i;
        j=j+(j&(-j));
        if (j>n) continue;
        c[j]+=c[i];
    }
    int m;
    scanf("%d",&m);
    for (i=0;i<m;i++)
    {
        int k,x1,y1,aa,bb,cc,dd,x,y;
        scanf("%d%d%d%d%d%d%d%d%d",&k,&x1,&y1,&aa,&bb,&cc,&dd,&x,&y);
        int j;
        if (x1<n) change(dfn[x1],y1);
        for (j=1;j<k;j++)
        {
            x1=((long long)x1*aa+bb)%n;
            y1=((long long)y1*cc+dd)%1000000007;
            change(dfn[x1],y1);
        }
        long long sum=0;
        for (;;)
        {
            if (up[x]==up[y])
            {
                if (depth[x]<depth[y]) swap(x,y);
                sum+=query(dfn[y],dfn[x]);
                break;
            }
            else
            {
                if (depth[up[x]]<depth[up[y]]) swap(x,y);
                sum+=query(dfn[up[x]],dfn[x]);
                x=father[up[x]];
            }
        }
        cout<<sum<<'\n';
    }
    return 0;
}