长乐Day？.3

————爆零的一天

树状数组

T1：

把每一个x_i表示为k+x_1或k-x_1，可以用树形结构解决，每次更新w_i时就暴力dfs再加载一遍。查询就把给定的新方程转化成只有x_1的形式求解，复杂度O(n^2)，会T，40pts。

#include<bits/stdc++.h>
using namespace std;
int n,q,f[1000001],w[1000001],k[1000001],z[1000001];
vector<int>edge[1000001];
void dfs(int x,int dep)
{
    if(dep%2==1) z[x]=1;
    else z[x]=-1;
    k[x]=w[x]-k[f[x]];
    for(int i=0;i<edge[x].size();i++)
    {
        int y=edge[x][i];
        dfs(y,dep+1); 
    }
}
int main()
{
    freopen("equation.in","r",stdin);
    freopen("equation.out","w",stdout);
    cin>>n>>q;
    for(int i=2;i<=n;i++)
    {
        cin>>f[i]>>w[i];
        edge[f[i]].push_back(i); 
    }
    dfs(1,1);
    int op,a,b,c;
    while(q--)
    {
        cin>>op;
        if(op==1)
        {
            cin>>a>>b>>c;
            int t1=z[a]+z[b],t2=c-k[a]-k[b];
            if(t1==0&&t2!=0) cout<<"none"<<endl;
            else if(t1==0&&t2==0) cout<<"inf"<<endl;
            else if(t2%t1!=0) cout<<"none"<<endl;
            else cout<<t2/t1<<endl;
        }
        else
        {
            cin>>a>>b;
            w[a]=b;
            dfs(1,1);
        }
    }

    return 0;
}

RMQ

无

感觉这两场都有点难，剩下的题会尝试看题解改一下。