这一场比赛的经历也是比较有趣呢

00:00:00  Participant has been assigned to the room (assigned to) 7
00:09:21  B  Accepted [main tests]
00:16:37  A  Accepted [main tests]
00:27:48  C  Pretests passed [pretests]
01:30:44  E  Wrong answer on pretest 5 [pretests]
01:36:07  E  Wrong answer on pretest 5 [pretests]
01:42:57  E  Accepted [main tests]
01:43:49  A  has been locked
01:45:46  A  Unsuccessful hacking attempt of TooDifficuIt
02:09:46  C  Hacked by dnvtmf
02:10:41  C  Accepted [main tests]
02:11:01  C  has been locked
02:12:44  C  Successful hacking attempt of Na2a

经历:

B是个水题啊..看到题面短就把它拆了

A是个水题啊..看完题就把它拆了

C是个找规律题啊..

看着0/1 1/2 1/4 3/8 5/16 11/32 21/64

感觉右边是2^(n-1)

左边是2^(n-1)+1或-1 /3

...交了,过pretest

D..不会做

E..树链剖分..

超级麻烦的样子哦...写了350行..

然后..A看别人写%lld就hack上去了

Unsuccessful..不开心

比赛快结束的时候,C被hack了....

1分钟修改正确,2分钟后hack了另一个人..补分

但没超过Q..被虐了几分

第一次把div 1做的这么好!

涨Rating啦!可惜没冲上2200

纪念下人生中第一个AC的div 1 E

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<time.h>
#include<math.h>
#include<memory>
#include<vector>
#include<bitset>
#include<fstream>
#include<stdio.h>
#include<utility>
#include<string.h>
#include<iostream>
#include<stdlib.h>
#include<algorithm>
using namespace std;
vector<int> v[100005];
vector<int> ans[100005];
struct edge
{
    int y;
    edge * next;
};
edge * new_edge()
{
    static edge a[200005];
    static int top=0;
    return &a[top++];
}
edge * li[100005];
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 depth[100005];
int father[100005];
edge * prefer_edge[100005];
int dfn[100005];
int size[100005];
void dfs1(int x)
{
    edge * t;
    size[x]=1;
    int max_size=0;
    for (t=li[x];t!=0;t=t->next)
    {
        if (t->y==father[x])
        {
            continue;
        }
        depth[t->y]=depth[x]+1;
        father[t->y]=x;
        dfs1(t->y);
        size[x]+=size[t->y];
        if (size[t->y]>max_size)
        {
            max_size=size[t->y];
            prefer_edge[x]=t;
        }
    }
}
int vis[100005];
int up[100005];
void dfs2(int x)
{
    static int num=0;
    dfn[x]=num;
    vis[num]=x;
    num++;
    if (prefer_edge[x]==0) return;
    up[prefer_edge[x]->y]=up[x];
    dfs2(prefer_edge[x]->y);
    edge * t;
    for (t=li[x];t!=0;t=t->next)
    {
        if (t->y==father[x])
        {
            continue;
        }
        if (t==prefer_edge[x])
        {
            continue;
        }
        up[t->y]=t->y;
        dfs2(t->y);
    }
}
long long val[1<<20];
int val2[1<<20];
long long tag[1<<20];
void push_up(int num)
{
    if (val2[num*2+1]==-1)
    {
        val[num]=val[num*2+2];
        val2[num]=val2[num*2+2];
    }
    else if (val2[num*2+2]==-1)
    {
        val[num]=val[num*2+1];
        val2[num]=val2[num*2+1];
    }
    else if (val[num*2+1]<val[num*2+2])
    {
        val[num]=val[num*2+1];
        val2[num]=val2[num*2+1];
    }
    else if (val[num*2+2]<val[num*2+1])
    {
        val[num]=val[num*2+2];
        val2[num]=val2[num*2+2];
    }
    else if (val2[num*2+1]<val[num*2+2])
    {
        val[num]=val[num*2+1];
        val2[num]=val2[num*2+1];
    }
    else
    {
        val[num]=val[num*2+2];
        val2[num]=val2[num*2+2];
    }
}
void push_down(int num)
{
    if (tag[num]==0) return;
    val[num*2+1]+=tag[num];
    tag[num*2+1]+=tag[num];
    val[num*2+2]+=tag[num];
    tag[num*2+2]+=tag[num];
    tag[num]=0;
}
void change(int num,int l,int r,int l0,int r0,int k)
{
    if ((l0<=l)&&(r<=r0))
    {
        tag[num]+=k;
        val[num]+=k;
        return;
    }
    int mid=(l+r)/2;
    push_down(num);
    if (l0<mid) change(num*2+1,l,mid,l0,r0,k);
    if (mid<r0) change(num*2+2,mid,r,l0,r0,k);
    push_up(num);
}
void build_tree(int num,int l,int r)
{
    if (l==r-1)
    {
        tag[num]=0;
        if (v[vis[l]].size()==0)
        {
            val2[num]=-1;
            return;
        }
        val2[num]=v[vis[l]][v[vis[l]].size()-1];
        val[num]=val2[num];
        return;
    }
    int mid=(l+r)/2;
    build_tree(num*2+1,l,mid);
    build_tree(num*2+2,mid,r);
    push_up(num);
}
void change2(int num,int l,int r,int t)
{
    if (l==r-1)
    {
        if (v[vis[l]].size()==0)
        {
            val2[num]=-1;
            return;
        }
        v[vis[l]].pop_back();
        if (v[vis[l]].size()==0)
        {
            val2[num]=-1;
            return;
        }
        val[num]-=val2[num];
        val2[num]=v[vis[l]][v[vis[l]].size()-1];
        val[num]+=val2[num];
        return;
    }
    int mid=(l+r)/2;
    push_down(num);
    if (t<mid)
    {
        change2(num*2+1,l,mid,t);
    }
    else
    {
        change2(num*2+2,mid,r,t);
    }
    push_up(num);
}
long long ans1;
int ans2;
void update_ans(int num)
{
    if (ans2==-1)
    {
        ans1=val[num];
        ans2=val2[num];
    }
    else if (val2[num]==-1)
    {
        return;
    }
    else if (val[num]<ans1)
    {
        ans1=val[num];
        ans2=val2[num];
    }
    else if (ans1<val[num])
    {
        return;
    }
    else if (val2[num]<ans2)
    {
        ans1=val[num];
        ans2=val2[num];
    }
}
void query(int num,int l,int r,int l0,int r0)
{
    if ((l0<=l)&&(r<=r0))
    {
        update_ans(num);
        return;
    }
    int mid=(l+r)/2;
    push_down(num);
    if (l0<mid) query(num*2+1,l,mid,l0,r0);
    if (mid<r0) query(num*2+2,mid,r,l0,r0);
}
int n;
int querys(int x,int y)
{
    ans2=-1;
    for (;;)
    {
        if (up[x]==up[y])
        {
            if (depth[x]<depth[y]) swap(x,y);
            query(0,0,n,dfn[y],dfn[x]+1);
            return ans2;
        }
        else
        {
            if (depth[up[x]]<depth[up[y]]) swap(x,y);
            query(0,0,n,dfn[up[x]],dfn[x]+1);
            x=father[up[x]];
        }
    }
}
int a[100005];
int main()
{
    #ifdef absi2011
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    int m,q;
    scanf("%d%d%d",&n,&m,&q);
    int i;
    for (i=1;i<n;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        x--;
        y--;
        insert_edge(x,y);
    }
    for (i=0;i<m;i++)
    {
        int x;
        scanf("%d",&x);
        x--;
        a[i]=x;
    }
    for (i=m-1;i>=0;i--)
    {
        v[a[i]].push_back(i);
    }
    depth[0]=0;
    dfs1(0);
    up[0]=0;
    dfs2(0);
    int tot=0;
    build_tree(0,0,n);
    for (i=0;i<q;i++)
    {
        int x,y;
        int oper;
        scanf("%d",&oper);
        if (oper==1)
        {
            scanf("%d%d",&x,&y);
            x--;
            y--;
            int k;
            scanf("%d",&k);
            for (;;)
            {
                int t=querys(x,y);
                if (t!=-1)
                {
                    change2(0,0,n,dfn[a[t]]);
                    ans[tot].push_back(t);
                }
                else
                {
                    break;
                }
                k--;
                if (k==0) break;
            }
            tot++;
        }
        else
        {
            int x;
            scanf("%d",&x);
            x--;
            int k;
            scanf("%d",&k);
            change(0,0,n,dfn[x],dfn[x]+size[x],k);
        }
    }
    for (i=0;i<tot;i++)
    {
        printf("%d",(int)ans[i].size());
        int j;
        for (j=0;j<(int)ans[i].size();j++)
        {
            printf(" %d",ans[i][j]+1);
        }
        printf("\n");
    }
    return 0;
}