0_0_18289406_13261.cpp:1:5083: fatal error: GCC4.9.2/x86_64-w64-mingw32/include/c++/bits/stdc++.h>usin: Invalid argument
#include <bits/stdc++.h>using namespace std;typedef pair<int,int> Pair;const int maxn=40000+100;int mson[maxn],son[maxn],dep[maxn],fa[maxn],val[maxn];//重孩子，子节点数目，深度，父节点，边权值（以非父节点的节点编号为边的编号，如1->2父节点为1，则该边编号为2）int id[maxn],rid[maxn],top[maxn],cnt,root;//边哈希到线段树上的位置，与id数组含义相反，重链顶端节点vector<Pair> G[maxn];void dfs_1(int u){ mson[u]=0; son[u]=1; int si=G[u].size(); for(int i=0; i<si; ++i) { if(G[u][i].first!=fa[u]) { int v=G[u][i].first; val[v]=G[u][i].second; fa[v]=u; dep[v]=dep[u]+1; dfs_1(v); if(son[mson[u]]<son[v]) mson[u]=v; son[u]+=son[v]; } }}void dfs_2(int u, int ttop){ rid[cnt]=u; id[u]=cnt++; top[u]=ttop; if(mson[u]) dfs_2(mson[u], ttop); int si = G[u].size(); for(int i=0; i<si; ++i) { if(G[u][i].first!=mson[u] && G[u][i].first!=fa[u]) { dfs_2(G[u][i].first, G[u][i].first); } }}void init(int root){ cnt=1; fa[root]=root; dep[root]=1; dfs_1(root); dfs_2(root, root);}/**********************************/struct Node{ int l, r; int w; int cl, cr;} tree[maxn*4];void PushUp(int x){ tree[x].w=tree[x<<1].w+tree[x<<1|1].w; tree[x].cl=tree[x<<1].cl; tree[x].cr=tree[x<<1|1].cr; if(tree[x<<1].cr==tree[x<<1|1].cl) tree[x].w--;}void PushDown(int x){ //当涂色相同 if(tree[x].w==1) { tree[x<<1].w=tree[x<<1|1].w=1; tree[x<<1].cl=tree[x<<1].cr=tree[x].cl; tree[x<<1|1].cl=tree[x<<1|1].cr=tree[x].cr; }}void Build(int x, int L, int R){ tree[x].l=L; tree[x].r=R; tree[x].w=0; if(L==R) { tree[x].cl=tree[x].cr=val[rid[L]]; tree[x].w=1; return; } int m=(L+R)/2; if(L<=m) Build(x<<1,L,m); if(m<R) Build(x<<1|1,m+1,R); PushUp(x);}//对树链的操作void Update(int x, int L, int R, int w){ if(L<=tree[x].l&&tree[x].r<=R) { tree[x].w=1; tree[x].cl=tree[x].cr=w; return ; } PushDown(x); int m=(tree[x].l+tree[x].r)/2; if(L<=m) Update(x<<1,L,R,w); if(m<R) Update(x<<1|1,L,R,w); PushUp(x);}int Queue(int x, int L, int R){ if(L<=tree[x].l && tree[x].r<=R) { return tree[x].w; } PushDown(x); int m=(tree[x].l+tree[x].r)/2,f1=0,f2=0; //用F1,F2标记左右子树是否被搜过 int ans=0; if(L<=m) ans+=Queue(x<<1,L,R),f1=1; if(m<R) ans+=Queue(x<<1|1,L,R),f2=1; if(f1 && f2) { if(tree[x<<1].cr==tree[x<<1|1].cl) --ans; //若做右子树都被搜过且左子树右孩子的颜色等于右子树左孩子的颜色则答案减一 } return ans;}int Queue2(int x, int L, int R){ if(L<=tree[x].l && tree[x].r<=R) { return tree[x].cl; } PushDown(x); int m=(tree[x].l+tree[x].r)/2; if(L<=m) return Queue2(x<<1,L,R); if(m<R) return Queue2(x<<1|1,L,R);}int Queue_T(int u,int v){ int f1=top[u],f2=top[v]; int ans=0; int cpu=0, cpv=0, x; //cpu，cpv分别记录重链端点对应的边的颜色 while(f1!=f2) { if(dep[f1]>dep[f2]) { swap(f1,f2); swap(u,v); swap(cpu,cpv); } printf("%d %d %d %d\n",id[f1],id[u],id[f2],id[v]); ans+=Queue(1,id[f2],id[v]); //求出一条重链当中的颜色段数 x=Queue2(1,id[v],id[v]); //求出某条边的颜色 if(x==cpv) --ans; cpv=Queue2(1,id[f2],id[f2]); v=fa[f2]; f2=top[v]; } if(u!=v) { if(dep[u]>dep[v]) swap(u, v),swap(cpu, cpv); //对树链的询问 ans+=Queue(1,id[mson[u]],id[v]); x=Queue2(1,id[v],id[v]); if(x==cpv) --ans; x=Queue2(1,id[mson[u]],id[mson[u]]); if(x==cpu) --ans; } else if(cpu==cpv) --ans; return ans;}void Update_T(int u,int v,int col){ int f1=top[u],f2=top[v]; while(f1!=f2) { if(dep[f1]>dep[f2]) { swap(f1,f2); swap(u,v); } //对树链的询问 Update(1,id[f2],id[v],col); v=fa[f2]; f2=top[v]; } if(u!=v) { if(dep[u]>dep[v]) swap(u, v); //对树链的询问 Update(1,id[mson[u]],id[v],col); }}int main(){ int T,cas=1,n,m; while(scanf("%d%d",&n,&m)==2) { for(int i=0; i<maxn; ++i) G[i].clear(); int u,v,w; for(int i=0; i<n-1; ++i) { scanf("%d%d%d",&u,&v,&w); G[u].push_back(make_pair(v, w)); G[v].push_back(make_pair(u, w)); } root=1; init(root); for (int i=1;i<n;i++) { printf("%d %d\n",i,id[i]); } Build(1,1,cnt-1); char op[10]; while(m--) { scanf("%s%d%d",op,&u,&v); if(op[0]=='Q') printf("%d\n",Queue_T(u,v)); else scanf("%d",&w),Update_T(u,v,w); } } return 0;}/*11 31 2 22 3 11 7 21 4 23 5 23 6 15 8 25 9 37 10 210 11 4Query 5 11*/
|
