记录编号	161215	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[ZJOI 2015] 幻想乡战略游戏	最终得分	100
用户昵称	nodgd	是否通过	通过
代码语言	C++	运行时间	4.649 s
提交时间	2015-05-02 17:12:10	内存使用	6.44 MiB

#include <cstdio>
#include <cstdlib>
using namespace std;
const int maxn=100005,maxm=200005;
int N,M,ln,cEnt,tot_id;
long long tot_summ,cOst;
int x[maxm],y[maxm],z[maxm],next[maxm],last[maxn];
int fath[maxn],size[maxn],deep[maxn];
int son[maxn],anc[maxn],dis[maxn];
int lid[maxn],rid[maxn],summ[maxn];
inline void _getnum(int &xx)
{
    char tt=getchar();bool asd=false;
    while((tt<'0'||tt>'9')&&tt!='-')tt=getchar();
    if(tt=='-')asd=true,tt=getchar();
    for(xx=0;tt>='0'&&tt<='9';tt=getchar())xx=xx*10+(tt-'0');
    if(asd==true)xx=0-xx;
}
void _dfs1(int i,int fa)
{
    int j;
    size[i]=1;
    fath[i]=fa;
    deep[i]=deep[fa]+1;
    for(j=last[i];j>0;j=next[j])
        if(y[j]!=fa)
        {
            dis[y[j]]=dis[i]+z[j];
            _dfs1(y[j],i);
            size[i]+=size[y[j]];
            if(size[son[i]]<size[y[j]])
                son[i]=y[j];
        }
}
void _dfs2(int i,int ancc)
{
    int j;
    lid[i]=++tot_id;
    anc[i]=ancc;
    if(son[i]!=0)_dfs2(son[i],ancc);
    for(j=last[i];j>0;j=next[j])
        if(y[j]!=fath[i]&&y[j]!=son[i])
            _dfs2(y[j],y[j]);
    rid[i]=tot_id;
}
int _getlca(int u,int v)
{
    int t;
    while(anc[u]!=anc[v])
    {
        if(deep[anc[u]]>=deep[anc[v]])u=fath[anc[u]];
        else v=fath[anc[v]];
    }
    if(deep[u]>deep[v])return v;
    else return u;
}
int _getdis(int u,int v)
{
    int w=_getlca(u,v);
    return dis[u]+dis[v]-dis[w]*2;
}
void _modify()
{
    int i,j,u,v,t,d;
    long long derta;
    _getnum(u);_getnum(t);
    d=_getdis(u,cEnt);
    tot_summ+=t;
    cOst+=1ll*t*d;
    for(j=lid[u];j<=N;j+=(j&(-j)))summ[j]+=t;
    while(true)
    {
        u=cEnt;
        for(i=last[u];i>0;i=next[i])
        {
            v=y[i];
            if(fath[u]==v)
            {
                t=0;
                for(j=rid[u];j>=1;j-=(j&(-j)))t+=summ[j];
                for(j=lid[u]-1;j>=1;j-=(j&(-j)))t-=summ[j];
                derta=1ll*z[i]*(t*2-tot_summ);
            }
            else
            {
                t=0;
                for(j=rid[v];j>=1;j-=(j&(-j)))t+=summ[j];
                for(j=lid[v]-1;j>=1;j-=(j&(-j)))t-=summ[j];
                derta=1ll*z[i]*(tot_summ-t*2);
            }
            if(derta<0)break;
        }
        if(derta>=0)break;
        cEnt=v;
        cOst+=derta;
    }
    printf("%lld\n",cOst);
}
int main()
{
    freopen("zjoi15_tree.in","r",stdin);
    freopen("zjoi15_tree.out","w",stdout);
    int i,j,k,t;
    _getnum(N);_getnum(M);
    for(i=j=1;i<N;i++)
    {
        _getnum(x[j]);_getnum(y[j]);_getnum(z[j]);
        next[j]=last[x[j]];last[x[j]]=j++;
        x[j]=y[j-1];y[j]=x[j-1];z[j]=z[j-1];
        next[j]=last[x[j]];last[x[j]]=j++;
    }
    _dfs1(1,0);
    _dfs2(1,1);
    cEnt=1;
    for(i=1;i<=M;i++)_modify();
    return 0;
}