[BZOJ 1511]Periods of Words

很妙的一道题啊。

这个题可以先求一遍KMP的失配函数,然后对于每个失配函数沿着失配边往前一直走(不能走到0)。然后对于每个前缀[tex]i[/tex],答案就是[tex]i-f[i][/tex](要求[tex]f[i][/tex]不为0,反之无解)。

为什么这样可以呢?

首先建议大家看一下Matrix67关于KMP的解释。对于一个前缀,如果整个弄上去肯定不行。所以说需要前面和后面重叠一个字串,这个子串是不考虑的。当然,我们希望在这个被删除的子串最短辣。

代码:

/**************************************************************
    Problem: 1511
    User: danihao123
    Language: C++
    Result: Accepted
    Time:148 ms
    Memory:5704 kb
****************************************************************/
 
#include <cstdio>
const int maxn=1000005;
 
char buf[maxn];
int f[maxn];
int main(){
    register int i,j;
    register long long ans=0;
    int n;
    scanf("%d%s",&n,buf);
    f[0]=f[1]=0;
    for(i=1;i<n;i++){
        j=f[i];
        while(j && buf[i]!=buf[j])
            j=f[j];
        f[i+1]=(buf[i]==buf[j]?j+1:0);
    }
    for(i=2;i<=n;i++){
        if(f[i]){
            while(f[f[i]]){
                f[i]=f[f[i]];
            }
        }
    }
    for(i=1;i<=n;i++){
        if(f[i]){
            ans+=i-f[i];
        }
    }
    printf("%lld\n",ans);
    return 0;
}

[BZOJ 1212]L语言

这个感觉本质上和那个Remember a Word很像吧……

不过这个只是求最长可行前缀,递推即可。

代码:

/**************************************************************
    Problem: 1212
    User: danihao123
    Language: C++
    Result: Accepted
    Time:660 ms
    Memory:45072 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
const int maxn=1048581;
const int maxW=4005,maxL=105;
#define REP(i,n) for(i=0;i<(n);i++)
#define REP_B(i,n) for(i=1;i<=(n);i++)
#define DREP(i,n) for(i=(n)-1;i>=0;i--)
#define CL_ARR(x,v) memset(x,v,sizeof(x))
 
vector<int> AnsList;
namespace Trie{
    const int maxnode=400005;
    const int sigma_siz=26;
    int Tree[maxnode][sigma_siz];
    int val[maxnode];
    int siz;
    inline int idx(char c){
        return c-'a';
    }
    inline void InitTrie(){
        siz=0;
        val[0]=0;
        CL_ARR(Tree[0],0);
    }
    void Insert(char *s,int v){
        register int u=0,n=strlen(s);
        register int i,c;
        REP(i,n){
            c=idx(s[i]);
            if(!Tree[u][c]){
                siz++;
                Tree[u][c]=siz;
                val[siz]=0;
                CL_ARR(Tree[siz],0);
            }
            u=Tree[u][c];
        }
        val[u]=v;
    }
    void Query(char *s,int len){
        register int i,c,u=0;
        AnsList.clear();
        REP(i,len){
            if(!s[i])
                break;
            c=idx(s[i]);
            if(!Tree[u][c])
                break;
            u=Tree[u][c];
            if(val[u])
                AnsList.push_back(val[u]);
        }
    }
};
 
char Text[maxn];
int len[maxW];
char buf[maxL];
bool d[maxn];
int main(){
    int n,m;
    int length;
    register int i,j,k;
    bool flag;
    Trie::InitTrie();
    scanf("%d%d",&n,&m);
    REP_B(i,n){
        scanf("%s",buf);
        len[i]=strlen(buf);
        Trie::Insert(buf,i);
    }
    REP_B(i,m){
        scanf("%s",Text);
        length=strlen(Text);
        CL_ARR(d,0);
        d[0]=true;
        for(j=0;j<=length;j++){
            if(d[j]){
                Trie::Query(Text+j,length-j);
                REP(k,AnsList.size()){
                    d[j+len[AnsList[k]]]=true;
                }
            }
        }
        flag=false;
        for(j=length;j>=0;j--){
            if(d[j]){
                flag=true;
                printf("%d\n",j);
                break;
            }
        }
        if(!flag)
            puts("0");
    }
    return 0;
}

[BZOJ 2081]Beads

Hash第一题……

这个题直接枚举串长Hash判断即可。不过,注意读题。

感觉Hash挺简单的。还有就是我用了wyy的生日做Hash种子辣!

代码:

/**************************************************************
    Problem: 2081
    User: danihao123
    Language: C++
    Result: Accepted
    Time:5636 ms
    Memory:10904 kb
****************************************************************/
 
#include <cstdio>
#include <set>
#include <vector>
using namespace std;
typedef unsigned long long ull;
const int maxn=200005;
const ull x=200261;
ull s[maxn];
ull sufHash[maxn],preHash[maxn],x_pow[maxn];
int n;
inline void InitHash(){
    register int i;
    for(i=n;i>=1;i--){
        sufHash[i]=s[i]+sufHash[i+1]*x;
    }
    for(i=1;i<=n;i++){
        preHash[i]=s[i]+preHash[i-1]*x;
    }
    x_pow[0]=1;
    for(i=1;i<=n;i++){
        x_pow[i]=x*x_pow[i-1];
    }
}
inline ull Hash(int i,int L){
    return sufHash[i]-x_pow[L]*sufHash[i+L];
}
inline ull FilpHash(int i,int L){
    return preHash[i+L-1]-x_pow[L]*preHash[i-1];
}
 
set<ull> S;
vector<int> AnsList;
int tot=0;
inline void Check(int k){
    register int i,ans=0;
    register ull h;
    S.clear();
    for(i=1;(i+k-1)<=n;i+=k){
        h=Hash(i,k)*FilpHash(i,k);
        if(!S.count(h)){
            S.insert(h);
            ans++;
        }
    }
    if(ans>tot){
        tot=ans;
        AnsList.clear();
        AnsList.push_back(k);
    }else{
        if(ans==tot)
            AnsList.push_back(k);
    }
}
 
int main(){
    register int i,ans=0,maxv=0,cnt,temp;
    bool flag;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
        scanf("%llu",&s[i]);
    InitHash();
    for(i=1;i<=n;i++){
        Check(i);
    }
    printf("%d %d\n",tot,AnsList.size());
    flag=false;
    for(i=0;i<AnsList.size();i++){
        if(flag)
            putchar(' ');
        flag=true;
        printf("%d",AnsList[i]);
    }
    putchar('\n');
    return 0;
}

[BZOJ 2118]墨墨的等式

论如何把数论乱搞和图论乱搞出在一起……

这个题由于要求[tex]x\ge 0[/tex],所以不能gcd乱搞。我们可以先取[tex]\{a_n\}[/tex]的最小值[tex]p[/tex](忽略为0的情况,为啥取最小值待会再说),对方程两边模[tex]p[/tex]。然后对于任何能使某个同余方程成立的[tex]\{x_n\}[/tex],将其中所有[tex]x_i[/tex]同时加任意个[tex]p[/tex],同余方程都成立。

取模后,[tex]B\in Z_p[/tex],所以说只要对于[tex]Z_p[/tex]中的每个数找出最小的一组合法解即能推出其他解(所以说,剩余系越少效率越高,这也就要求取的[tex]a_i[/tex]要小)。不过这个最小的一组合法解怎么找?

我们先找出任意一个合法[tex]B[/tex](比如说0吧),然后尝试加上[tex]a_i[/tex],就可以推出其他[tex]B\in Z_p[/tex]的最小解。这个应用当然是需要最短路辣。

求出来的最短路,表示的是取最小解时的[tex]B[/tex]。这样的话就可以推出某个前缀区间中合法[tex]B[/tex]的个数(能加多少[tex]p[/tex],就有多少个,注意不要忽略加0个的情况),并且答案符合区间减法,最后做差分即可。

注意忽略[tex]a_i=0[/tex]的情况(相当于不存在)。

代码:

/**************************************************************
    Problem: 2118
    User: danihao123
    Language: C++
    Result: Accepted
    Time:1952 ms
    Memory:5508 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
#ifdef DEBUG
#include <cassert>
#endif
using namespace std;
typedef long long ll;
const int maxn=15;
const ll INF=0x7f7f7f7f7f7f7f7f;
ll A[maxn];
bool inQueue[500005];
ll d[500005];
int n;
ll minv;
inline void SPFA(){
    register int i,u,to;
    queue<int> Q;
    memset(d,0x7f,sizeof(d));
    d[0]=0;
    Q.push(0);
    inQueue[0]=true;
    #ifdef DEBUG
    assert(d[1]==INF);
    #endif
    while(!Q.empty()){
        u=Q.front();
        Q.pop();
        inQueue[u]=false;
        for(i=1;i<=n;i++){
            to=(u+A[i])%minv;
            if(d[u]<INF && d[u]+A[i]<d[to]){
                d[to]=d[u]+A[i];
                if(!inQueue[to]){
                    Q.push(to);
                    inQueue[to]=true;
                }
            }
        }
    }
}
 
inline ll Calc(ll x){
    register ll ans=0;
    register int i=0;
    for(i=0;i<minv;i++)
        if(d[i]<=x)
            ans+=(x-d[i])/minv+1;
    return ans;
}
 
int main(){
    ll l,r;
    register int i;
    scanf("%d%lld%lld",&n,&l,&r);
    minv=0x7fffffff;
    for(i=1;i<=n;i++){
        scanf("%d",&A[i]);
        if(!A[i]){
            i--;
            n--;
            continue;
        }
        minv=min(minv,A[i]);
    }
    SPFA();
    printf("%lld\n",Calc(r)-Calc(l-1));
    return 0;
}


[BZOJ 1217]消防局的设立

很明显可以看出消防局距离为5的话最划算……然后贪心就行了,顺便注意下根节点处理

代码:

/**************************************************************
    Problem: 1217
    User: danihao123
    Language: C++
    Result: Accepted
    Time:0 ms
    Memory:844 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=1010;
#define GRAPH_REP(i,u) for(i=first[u];i;i=next[i])
int first[maxn];
int next[maxn*2],to[maxn*2];
int graph_cnt=0;
inline void AddEdge(int u,int v){
    graph_cnt++;
    next[graph_cnt]=first[u];
    first[u]=graph_cnt;
    to[graph_cnt]=v;
}
 
int ans=0;
int d[maxn];
void dfs(int x,int fa=-1){
    int maxq=-maxn,minq=maxn;
    int i;
    GRAPH_REP(i,x)
        if(to[i]!=fa){
            dfs(to[i],x);
            maxq=max(maxq,d[to[i]]);
            minq=min(minq,d[to[i]]);
        }
    if(minq+maxq<=3)
        d[x]=minq+1;
    else
        d[x]=maxq+1;
    if(minq==maxn)
        d[x]=3;
    if(d[x]==5){
        ans++;
        d[x]=0;
    }else{
        if(fa==-1 && d[x]>2)
            ans++;
    }
}
 
int main(){
    int n,v;
    register int i;
    scanf("%d",&n);
    for(i=1;i<=(n-1);i++){
        scanf("%d",&v);
        AddEdge(i+1,v);
        AddEdge(v,i+1);
    }
    dfs(1);
    printf("%d\n",ans);
    return 0;
}

[BZOJ 1711]吃饭

这道题当初竟然没A……so sad

这题的建图要这么来:吃的、喝的、牛什么的统统拉进图里(不过牛本身只能同时享受一种食物,所以说点容量为1,要拆成俩点)。对于吃的,从[tex]S[/tex]向每个吃的连一条边。喝的每个向[tex]T[/tex]连一条边。牛本身按照喜好连即可(注意要拆成俩点!)。

代码:

/**************************************************************
    Problem: 1711
    User: danihao123
    Language: C++
    Result: Accepted
    Time:20 ms
    Memory:864 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
const int maxn=405,INF=0x7f7f7f7f;
 
namespace Dinic{
    struct Edge{
        int u,v,cap,flow;
    };
    vector<Edge> edges;
    vector<int> G[maxn];
    int m;
    inline void AddEdge(int u,int v,int cap){
        edges.push_back((Edge){u,v,cap,0});
        edges.push_back((Edge){v,u,0,0});
        m=edges.size();
        G[u].push_back(m-2);
        G[v].push_back(m-1);
    }
    bool vis[maxn];
    int d[maxn];
    int s,t;
    bool BFS(){
        register int i,x;
        queue<int> Q;
        memset(vis,0,sizeof(vis));
        d[s]=0;
        Q.push(s);
        vis[s]=true;
        while(!Q.empty()){
            x=Q.front();
            Q.pop();
            for(i=0;i<G[x].size();i++){
                Edge& e=edges[G[x][i]];
                if(!vis[e.v] && e.cap>e.flow){
                    d[e.v]=d[x]+1;
                    Q.push(e.v);
                    vis[e.v]=true;
                }
            }
        }
        return vis[t];
    }
    int cur[maxn];
    int DFS(int x,int a){
        if(x==t || a==0)
            return a;
        int flow=0,f;
        for(int& i=cur[x];i<G[x].size();i++){
            Edge& e=edges[G[x][i]];
            if(d[e.v]==d[x]+1){
                f=DFS(e.v,min(a,e.cap-e.flow));
                if(f>0){
                    flow+=f;
                    e.flow+=f;
                    edges[G[x][i]^1].flow-=f;
                    a-=f;
                    if(a==0)
                        break;
                }
            }
        }
        return flow;
    }
    inline int Maxflow(int S,int T){
        register int ans=0;
        s=S;
        t=T;
        while(BFS()){
            memset(cur,0,sizeof(cur));
            ans+=DFS(s,INF);
        }
        return ans;
    }
};
int main(){
    int N,F,D,f,d,x;
    register int i,j,t;
    scanf("%d%d%d",&N,&F,&D);
    t=2*N+F+D+1;
    for(i=1;i<=F;i++)
        Dinic::AddEdge(0,i,1);
    for(i=2*N+F+1;i<t;i++)
        Dinic::AddEdge(i,t,1);
    for(i=1;i<=N;i++)
        Dinic::AddEdge(F+2*i-1,F+2*i,1);
    for(i=1;i<=N;i++){
        scanf("%d%d",&f,&d);
        for(j=1;j<=f;j++){
            scanf("%d",&x);
            Dinic::AddEdge(x,2*i-1+F,1);
        }
        for(j=1;j<=d;j++){
            scanf("%d",&x);
            Dinic::AddEdge(2*i+F,F+2*N+x,1);
        }
    }
    printf("%d\n",Dinic::Maxflow(0,t));
    return 0;
}

[BZOJ 2190]仪仗队

这个题啊……有规律可循。

我们可以发现,关于答案[tex]a[/tex]有如下规律:

[tex]a+1=2\mul (\Sigma_{i=2}^{n-1}\varphi(i)+2)[/tex]

然后筛法求欧拉函数即可(我听说神犇们都用了杜教筛哎)

代码:

/**************************************************************
    Problem: 2190
    User: danihao123
    Language: C++
    Result: Accepted
    Time:28 ms
    Memory:976 kb
****************************************************************/
 
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn=40005;
#define CUS_REP(i,a,b) for(i=(a);i<=(b);i++)
 
int phi[maxn];
int n;
void sieve(){
    register int i,j;
    phi[1]=1;
    CUS_REP(i,2,n)
        if(!phi[i])
            for(j=i;j<=n;j+=i){
                if(!phi[j])
                    phi[j]=j;
                phi[j]=phi[j]/i*(i-1);
            }
}
 
int main(){
    register int i,ans=2;
    scanf("%d",&n);
    sieve();
    /*
    #ifdef DEBUG
    CUS_REP(i,1,n)
        printf("%d\n",phi[i]);
    #endif
    */
    CUS_REP(i,2,n-1)
        ans+=phi[i];
    printf("%d\n",ans*2-1);
    return 0;
}


[BZOJ 1520]Szk-Schools

这个是二分图最小权完美匹配啦……不过我还是写的费用流。

不过注意一定要判断是否有完美匹配。

代码:

/**************************************************************
    Problem: 1520
    User: danihao123
    Language: C++
    Result: Accepted
    Time:2016 ms
    Memory:5004 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn=410;
namespace MCMF{
    struct Edge{
        int u,v,cap,flow,cost;
    };
    vector<Edge> edges;
    vector<int> G[maxn];
    int m;
    inline void AddEdge(int u,int v,int cap,int cost){
        edges.push_back((Edge){u,v,cap,0,cost});
        edges.push_back((Edge){v,u,0,0,-cost});
        m=edges.size();
        G[u].push_back(m-2);
        G[v].push_back(m-1);
    }
    inline void ClearGraph(){
        register int i;
        edges.clear();
        for(i=0;i<maxn;i++)
            G[i].clear();
    }
    int a[maxn];
    bool inQueue[maxn];
    int d[maxn],p[maxn];
    bool BellmanFord(int s,int t,int& flow,long long& cost){
        register int i,u;
        queue<int> Q;
        memset(d,0x7f,sizeof(d));
        memset(inQueue,0,sizeof(inQueue));
        d[s]=0;
        inQueue[s]=true;
        p[s]=0;
        a[s]=0x7f7f7f7f;
        Q.push(s);
        while(!Q.empty()){
            u=Q.front();
            Q.pop();
            inQueue[u]=false;
            for(i=0;i<G[u].size();i++){
                Edge& e=edges[G[u][i]];
                if(e.cap>e.flow && d[e.v]>d[u]+e.cost){
                    d[e.v]=d[u]+e.cost;
                    p[e.v]=G[u][i];
                    a[e.v]=min(a[u],e.cap-e.flow);
                    if(!inQueue[e.v]){
                        Q.push(e.v);
                        inQueue[e.v]=true;
                    }
                }
            }
        }
        if(d[t]==0x7f7f7f7f)
            return false;
        flow+=a[t];
        cost+=((long long)d[t])*((long long)a[t]);
        for(u=t;u!=s;u=edges[p[u]].u){
            edges[p[u]].flow+=a[t];
            edges[p[u]^1].flow-=a[t];
        }
        return true;
    }
    long long MincostMaxflow(int s,int t,int& flow){
        register long long ans=0;
        while(BellmanFord(s,t,flow,ans));
        return ans;
    }
};
int main(){
    int n,m,a,b,k;
    register int i,j,cost,flow=0;
    register long long ans;
    scanf("%d",&n);
    for(i=1;i<=n;i++){
        scanf("%d%d%d%d",&m,&a,&b,&k);
        for(j=a;j<=b;j++){
            cost=k*abs(j-m);
            MCMF::AddEdge(i,j+n,1,cost);
        }
    }
    for(i=1;i<=n;i++)
        MCMF::AddEdge(0,i,1,0);
    for(i=n+1;i<=2*n;i++)
        MCMF::AddEdge(i,2*n+1,1,0);
    ans=MCMF::MincostMaxflow(0,2*n+1,flow);
    if(flow<n)
        puts("NIE");
    else
        printf("%lld\n",ans);
    return 0;
}

[BZOJ 1934]善意的投票/[BZOJ 2768]冠军调查

这个是一道题啊……不过都是挺经典的问题……

建图是这样的:支持0的从[tex]S[/tex]向此点连一条容量为1的边,支持1的就向[tex]T[/tex]连一条长度为1的边,朋友之间连一条长度为1的边。跑一遍最小割即可。

这个的解释?最优情况下任何人违背自己的意见都是因为怕和朋友冲突,和朋友冲突则是因为没有违背自己的意见(废话)。所以拆了最小割就解决掉了所有冲突问题。

代码:

/**************************************************************
    Problem: 2768
    User: danihao123
    Language: C++
    Result: Accepted
    Time:60 ms
    Memory:7668 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn=305;
namespace Dinic{
    struct Edge{
        int u,v,cap,flow;
    };
    vector<Edge> edges;
    vector<int> G[maxn];
    int s,t;
    int m;
    inline void AddEdge(int u,int v,int cap){
        edges.push_back((Edge){u,v,cap,0});
        edges.push_back((Edge){v,u,0,0});
        m=edges.size();
        G[u].push_back(m-2);
        G[v].push_back(m-1);
    }
    bool vis[maxn];
    int cur[maxn],d[maxn];
    bool bfs(){
        register int i,u;
        queue<int> Q;
        memset(vis,0,sizeof(vis));
        Q.push(s);
        d[s]=0;
        vis[s]=true;
        while(!Q.empty()){
            u=Q.front();
            Q.pop();
            for(i=0;i<G[u].size();i++){
                Edge& e=edges[G[u][i]];
                if(!vis[e.v] && e.cap>e.flow){
                    d[e.v]=d[u]+1;
                    Q.push(e.v);
                    vis[e.v]=true;
                }
            }
        }
        return vis[t];
    }
    int dfs(int x,int a){
        if(x==t || a==0)
            return a;
        int f,flow=0;
        for(int& i=cur[x];i<G[x].size();i++){
            Edge& e=edges[G[x][i]];
            if((d[x]+1==d[e.v]) && ((f=dfs(e.v,min(a,e.cap-e.flow)))>0)){
                flow+=f;
                e.flow+=f;
                edges[G[x][i]^1].flow-=f;
                a-=f;
                if(a==0)
                    break;
            }
        }
        return flow;
    }
    int MinCut(int S,int T){
        register int ans=0;
        s=S;
        t=T;
        while(bfs()){
            memset(cur,0,sizeof(cur));
            ans+=dfs(s,0x7fffffff);
        }
        return ans;
    }
};
int main(){
    int n,m;
    int u,v;
    register int i;
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++){
        scanf("%d",&u);
        if(!u){
            Dinic::AddEdge(0,i,1);
        }else{
            Dinic::AddEdge(i,n+1,1);
        }
    }
    for(i=1;i<=m;i++){
        scanf("%d%d",&u,&v);
        Dinic::AddEdge(u,v,1);
        Dinic::AddEdge(v,u,1);
    }
    printf("%d\n",Dinic::MinCut(0,n+1));
    return 0;
}

[BZOJ 3531]旅行

发现自己好久没写树链剖分了……唉……

言归正传,这道题很容易想到的做法就是每种宗教开一个线段树,到各个宗教的线段树里面操作即可。

很可惜,直接开线段树的话肯定会MLE。我们可以考虑动态开点,对于不需要的点一律不开。这样内存消耗量就大减了。

注意一些细节:

  1. 查询时判断当前结点是不是NULL。
  2. 删除前最好判断一下这个结点是不是NULL吧,以防万一。
  3. 删除操作时,如果结点没有用了,就删。但是注意,记得delete前要把原指针设为NULL,直接delete会引起悬垂指针问题导致爆炸!

代码:

/**************************************************************
    Problem: 3531
    User: danihao123
    Language: C++
    Result: Accepted
    Time:10404 ms
    Memory:34872 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=100005;
int n;
namespace SegmentTree{
    struct Node{
        int sumv,maxv;
        Node *lc,*rc;
        Node(){
            sumv=maxv=0;
            lc=rc=NULL;
        }
        void maintain(){
            if(lc!=NULL){
                if(rc!=NULL){
                    sumv=lc->sumv+rc->sumv;
                    maxv=max(lc->maxv,rc->maxv);
                }else{
                    sumv=lc->sumv;
                    maxv=lc->maxv;
                }
            }else{
                if(rc!=NULL){
                    sumv=rc->sumv;
                    maxv=rc->maxv;
                }
            }
        }
    };
    Node* T[maxn];
    int p,v;
    void _Delete(Node* &o,int L,int R){
        if(o==NULL)
            return;
        if(L==R){
            Node *temp=o;
            o=NULL;
            delete temp;
        }else{
            int M=L+(R-L)/2;
            if(p<=M)
                _Delete(o->lc,L,M);
            else
                _Delete(o->rc,M+1,R);
            if(o->lc==NULL && o->rc==NULL){
                Node *temp=o;
                o=NULL;
                delete temp;
            }else{
                o->maintain();
            }
        }
    }
    inline void Delete(int c,int pos){
        p=pos;
        _Delete(T[c],1,n);
    }
    void _Insert(Node* &o,int L,int R){
        if(o==NULL)
            o=new Node();
        if(L==R){
            o->sumv=o->maxv=v;
        }else{
            int M=L+(R-L)/2;
            if(p<=M)
                _Insert(o->lc,L,M);
            else
                _Insert(o->rc,M+1,R);
        }
        o->maintain();
    }
    inline void Insert(int c,int pos,int value){
        p=pos;
        v=value;
        _Insert(T[c],1,n);
    }
    int ql,qr;
    int _query_max(Node *o,int L,int R){
        if(o==NULL)
            return 0;
        if(ql<=L && R<=qr)
            return o->maxv;
        int M=L+(R-L)/2,ans=0;
        if(ql<=M)
            ans=max(ans,_query_max(o->lc,L,M));
        if(qr>M)
            ans=max(ans,_query_max(o->rc,M+1,R));
        return ans;
    }
    inline int query_max(int c,int l,int r){
        ql=l;
        qr=r;
        return _query_max(T[c],1,n);
    }
    int _query_sum(Node *o,int L,int R){
        if(o==NULL)
            return 0;
        if(ql<=L && R<=qr)
            return o->sumv;
        int M=L+(R-L)/2,ans=0;
        if(ql<=M)
            ans+=_query_sum(o->lc,L,M);
        if(qr>M)
            ans+=_query_sum(o->rc,M+1,R);
        return ans;
    }
    inline int query_sum(int c,int l,int r){
        ql=l;
        qr=r;
        return _query_sum(T[c],1,n);
    }
};
#define REP(i,n) for(i=0;i<(n);i++)
#define REP_B(i,n) for(i=1;i<=(n);i++)
#define GRAPH_REP(i,u) for(i=first[(u)];i;i=next[i])
int first[maxn];
int next[maxn*2],to[maxn*2];
int graph_tot=0;
inline void AddEdge(int u,int v){
    graph_tot++;
    next[graph_tot]=first[u];
    first[u]=graph_tot;
    to[graph_tot]=v;
}
 
int dep[maxn],fa[maxn],son[maxn],siz[maxn];
bool vis[maxn];
void dfs_1(int x,int father,int depth){
    vis[x]=true;
    fa[x]=father;
    dep[x]=depth;
    siz[x]=1;
    int i,temp,max_siz=0;
    GRAPH_REP(i,x){
        temp=to[i];
        if(!vis[temp]){
            dfs_1(temp,x,depth+1);
            siz[x]+=siz[temp];
            if(siz[temp]>max_siz){
                son[x]=temp;
                max_siz=siz[temp];
            }
        }
    }
}
int hld_cnt=0;
int rlg[maxn];
int d[maxn];
int tid[maxn],top[maxn];
void dfs_2(int x,int a){
    vis[x]=true;
    top[x]=a;
    tid[x]=++hld_cnt;
    SegmentTree::Insert(rlg[x],hld_cnt,d[x]);
    if(son[x])
        dfs_2(son[x],a);
    else
        return;
    int i,temp;
    GRAPH_REP(i,x){
        temp=to[i];
        if(!vis[temp]){
            dfs_2(temp,temp);
        }
    }
}
int query_max(int c,int x,int y){
    if(top[x]==top[y]){
        if(tid[x]>tid[y])
            swap(x,y);
        return SegmentTree::query_max(c,tid[x],tid[y]);
    }
    if(dep[top[x]]<dep[top[y]])
        swap(x,y);
    return max(SegmentTree::query_max(c,tid[top[x]],tid[x]),query_max(c,fa[top[x]],y));
}
int query_sum(int c,int x,int y){
    if(top[x]==top[y]){
        if(tid[x]>tid[y])
            swap(x,y);
        return SegmentTree::query_sum(c,tid[x],tid[y]);
    }
    if(dep[top[x]]<dep[top[y]])
        swap(x,y);
    return SegmentTree::query_sum(c,tid[top[x]],tid[x])+query_sum(c,fa[top[x]],y);
}
inline void Replace(int pos,int direction){
    int c=rlg[pos];
    SegmentTree::Delete(c,tid[pos]);
    SegmentTree::Insert(direction,tid[pos],d[pos]);
    rlg[pos]=direction;
}
inline void Update(int pos,int v){
    d[pos]=v;
    SegmentTree::Insert(rlg[pos],tid[pos],v);
}
 
int main(){
    register int i;
    int q,u,v;
    char buf[5];
    scanf("%d%d",&n,&q);
    REP_B(i,n){
        scanf("%d%d",&d[i],&rlg[i]);
    }
    REP_B(i,n-1){
        scanf("%d%d",&u,&v);
        AddEdge(u,v);
        AddEdge(v,u);
    }
    dfs_1(1,0,1);
    memset(vis,0,sizeof(vis));
    dfs_2(1,1);
    while(q--){
        memset(buf,0,sizeof(buf));
        scanf("%s%d%d",buf,&u,&v);
        if(buf[0]=='C'){
            if(buf[1]=='W'){
                Update(u,v);
            }else{
                Replace(u,v);
            }
        }else{
            if(buf[1]=='M'){
                printf("%d\n",query_max(rlg[u],u,v));
            }else{
                printf("%d\n",query_sum(rlg[u],u,v));
            }
        }
    }
    return 0;
}