SPOJ2666. Query on a tree IV
7559 단어 query
You are given a tree (an acyclic undirected connected graph) with N nodes, and nodes numbered 1,2,3...,N. Each edge has an integer value assigned to it(note that the value can be negative). Each node has a color, white or black. We define dist(a, b) as the sum of the value of the edges on the path from node a to node b.
All the nodes are white initially.
We will ask you to perfrom some instructions of the following form:
Input
Output
For each "A"operation, write one integer representing its result. If there is no white node in the tree, you should write "They have disappeared.".
Example
Input:
3
1 2 1
1 3 1
7
A
C 1
A
C 2
A
C 3
A
Output:
2
2
0
They have disappeared.
--------------------------------------------------------
: 。
: 。 , , , , , 。
/*
:SPOJ2666. Query on a tree IV
: +
: +
, ,
, , 。 ,
, O(n) ,
, 6*N ,
, , pn[t], t
pn[t]+1, :son[i] i
,fa[i] i ,top[i] i ,
siz[i] i ,cp[i] i ,cd[i] i
,csz[i] i ,pn[i] i ,
cid[i] t (i-pn[t]) ,cnum ,pnum
。
,
*/
#include <stdio.h>
#include <string.h>
#include <queue>
#define clr(a,b) memset(a,b,sizeof(a))
using namespace std;
const int N=200005,M=7*N,inf=0x7fffffff;
struct Node{
int v,p;
bool operator<(const Node & a)const{
return v<a.v;
}
Node(int a,int b):v(a),p(b){}
};
int n,eid;
int head[N],ed[N<<1],val[N<<1],nxt[N<<1];
int son[N],fa[N],top[N],siz[N],dis[N],col[N];
int cp[N],cd[N],csz[N],pn[N],cid[M],cnum,pnum;
int le[M],ri[M],maxl[M],maxr[M],opt[M];
priority_queue<Node>que[N],allque;
void addedge(int s,int e,int v){
ed[eid]=e;val[eid]=v;nxt[eid]=head[s];head[s]=eid++;
}
int pl(int a,int b){
if(a==-inf||b==-inf)return -inf;
return a+b;
}
void dfs_1(int s,int f){
siz[s]=1;int maxx=0,p=-1;top[s]=s;fa[s]=f;
for(int i=head[s];~i;i=nxt[i]){
int e=ed[i];if(e==f){fa[s]=i;continue;}
dfs_1(e,s);siz[s]+=siz[e];
if(siz[e]>maxx){maxx=siz[e];p=i;}
}
son[s]=p;
}
void buildtree(int p,int rt,int l,int r){
le[p+rt]=l;ri[p+rt]=r;int mid=(l+r)>>1;
maxl[p+rt]=maxr[p+rt]=opt[p+rt]=-inf;
if(l==r)return ;
buildtree(p,rt<<1,l,mid);
buildtree(p,rt<<1|1,mid+1,r);
}
void update(int p,int rt,int x){
int l=le[p+rt],r=ri[p+rt],mid=(l+r)>>1;
int root=p+rt,lroot=p+(rt<<1),rroot=p+(rt<<1|1);
if(l==x&&r==x){
int s=cid[p+x],d1=-inf,d2=-inf,p1=-1;
while(!que[s].empty()){
int v=que[s].top().v,ps=que[s].top().p;que[s].pop();
int e=cid[ps];
if(maxl[ps]+val[fa[e]]!=v)continue;
p1=ps;d1=v;break;
}
while(!que[s].empty()){
int v=que[s].top().v,ps=que[s].top().p,e=cid[ps];
if(maxl[ps]+val[fa[e]]!=v||ps==p1){que[s].pop();continue;}
d2=v;break;
}
if(~p1)que[s].push(Node(d1,p1));
if(col[s])maxl[root]=maxr[root]=max(d1,0);
else maxl[root]=maxr[root]=d1;
if(col[s])opt[root]=max(d1,pl(d1,d2));
else opt[root]=pl(d1,d2);
if(col[s])opt[root]=max(opt[root],0);
if(rt==1){
if(~fa[s]){
int f=ed[fa[s]],v=val[fa[s]];
if(maxl[root]!=-inf)que[f].push(Node(maxl[root]+v,root));
}
if(opt[root]!=-inf)allque.push(Node(opt[root],root));
}
return ;
}
if(x<=mid)update(p,rt<<1,x);
else update(p,rt<<1|1,x);
int dm0=dis[cid[p+mid]],dm1=dis[cid[p+mid+1]];
int dr=dis[cid[p+r]],dl=dis[cid[p+l]];
maxl[root]=max(maxl[lroot],pl(dm1-dl,maxl[rroot]));
maxr[root]=max(maxr[rroot],pl(dr-dm0,maxr[lroot]));
opt[root]=max(opt[lroot],opt[rroot]);
opt[root]=max(opt[root],pl(pl(maxl[rroot],maxr[lroot]),dm1-dm0));
int s=cid[p+1];
if(rt==1){
if(~fa[s]){
int f=ed[fa[s]],v=val[fa[s]];
if(maxl[root]!=-inf)que[f].push(Node(maxl[root]+v,root));
}
if(opt[root]!=-inf)allque.push(Node(opt[root],root));
}
}
void dfs_2(int s,int d,int c){
if(s==top[s]){cp[s]=++cnum;csz[cp[s]]=0;}
if(~son[s]){
top[ed[son[s]]]=top[s];dfs_2(ed[son[s]],d+val[son[s]],c+1);
}
for(int i=head[s];~i;i=nxt[i])
if(i!=son[s]&&i!=fa[s])dfs_2(ed[i],0,1);
cp[s]=cp[top[s]];cd[s]=c;int k=cp[s];
csz[k]=max(csz[k],cd[s]);dis[s]=d;
if(s==top[s]){
pn[k]=pnum;pnum+=6*csz[k];
int t=s,num=2;cid[pn[k]+1]=s;
while(~son[t]){
cid[pn[k]+num]=ed[son[t]];
t=ed[son[t]];num++;
}
}
}
void dfsinit(int s){
col[s]=1;
if(~son[s])dfsinit(ed[son[s]]);
for(int i=head[s];~i;i=nxt[i])
if(i!=fa[s]&&i!=son[s])dfsinit(ed[i]);
update(pn[cp[s]],1,cd[s]);
}
int main(){
// freopen("/home/axorb/in","r",stdin);
// freopen("/home/axorb/out","w",stdout);
scanf("%d",&n);eid=0;clr(head,-1);
for(int i=1;i<n;i++){
int a,b,c;scanf("%d%d%d",&a,&b,&c);
addedge(a,b,c);addedge(b,a,c);
}
dfs_1(1,-1);cnum=pnum=0;dfs_2(1,0,1);clr(col,0);
while(!allque.empty())allque.pop();
for(int i=1;i<=cnum;i++){
while(!que[i].empty())que[i].pop();buildtree(pn[i],1,1,csz[i]);
}
dfsinit(1);
// printf("%d
",allque.top().v);
int q;scanf("%d",&q);
while(q--){
char ss[20];scanf("%s",ss);
if(ss[0]=='A'){
int flag=0;
while(!allque.empty()){
int v=allque.top().v,p=allque.top().p;
if(opt[p]!=v){allque.pop();continue;}
printf("%d
",v);flag=1;break;
}
if(!flag)puts("They have disappeared.");
}
else{
int x;scanf("%d",&x);col[x]^=1;
while(top[x]!=1){
update(pn[cp[x]],1,cd[x]);x=ed[fa[top[x]]];
}
update(pn[cp[x]],1,cd[x]);
}
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
빠른 팁!!!안녕하세요 여러분 👋 요청을 할 때 모든 구성 요소에 동일한 코드를 작성하는 데 정말 지쳤습니다. 나는 일을 단순하게 만들고 싶고 내 생각에 당신도 원할 것입니다. 그런 것들에 대한 팁을 보려면 내 예를 확인하십시오...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.